DSA Lab
String search
Find every place a pattern appears in a text. The naive method tries every shift and recompares from scratch; KMP first learns how the pattern overlaps itself, so after a mismatch it slides forward without ever moving back in the text.
String search: how it works
In this tool: naive search vs KMP. Put in your own values and watch it change. Each operation runs one step at a time and says in plain words what happened, with its calculation worked out. The code is shown in Python, C, C++ or Java with the line that just ran marked, and an Understand it panel gives the idea, why it works, the cost of each operation, common mistakes and a short quiz.
Lessons that use it
- String matching: naive search and KMP (Algorithms)Find every place a pattern appears in a text: the simple O(n·m) method, and Knuth–Morris–Pratt, which never moves backwards in the text.