This app helps with visualising the behaviour of three classic string matching algorithms: the simple naive algorithm (which checks the pattern string for a match at all possible positions), the Knuth-Morris-Pratt (KMP) algorithm and the Boyer-Moore algorithm. The latter comes in two flavours: a simple version, known as Boyer-Moore-Horspool that uses only the Bad Character heuristic, and the full version using the Good Suffix heuristic as well.
The code for the full Boyer Moore algorithm has been translated from the C version at wiki.dreamrunner.org.
Since the Boyer-Moore implementations search only ASCII characters, all non-ASCII characters are removed from both the pattern and the strings when using those algorithms.
| i: | {{ i - 1 }} |
| Text: | {{ text[i - 1] }} |
| Pattern: | {{ patternChar(i - 1) }} |
| Text length (n) | {{n}} |
| Pattern length (m) | {{m}} |
| Text index (i) | {{i}} |
| Pattern index (j) | {{j}} |
| Pattern shift (i - j) | {{ i - j }} |
| Comparisons | {{ comparisonIndex + 1}} |
| Total comparisons | {{ comparisons.length }} |
| Num matches | {{ matches.length }} |
The above plot shows all the (i, j) indices of the character comparisons made during the whole algorithm. (i, j) are the indices into the text and the pattern, respectively. Gold stars show points where a match is detected. A red circle shows the current point in the simulation.