Write PatternSearch, which reads pairs of lines — a text, then a pattern — and finds all the positions where the pattern occurs (overlapping occurrences included), with two algorithms, counting the character comparisons of each.
- Naive: try every starting position and compare character by character. Up to n × m comparisons.
- Knuth–Morris–Pratt: first build the failure table of the pattern —
fail[k]is the length of the longest proper prefix ofpattern[0..k]that is also a suffix of it. During the search, after a mismatch, the pattern is shifted according to the table and the text index never moves back. About n + m comparisons.
For the input
the cat sat on the mat with the other cat
the
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
aaaaaaaab
abababababab
abab
hello world
xyz
the program prints
"the" in a text of 41 characters: found at [0, 15, 28, 33]
naive 52 comparisons, KMP 47 comparisons, same result: true
"aaaaaaaab" in a text of 41 characters: found at [32]
naive 297 comparisons, KMP 88 comparisons, same result: true
"abab" in a text of 12 characters: found at [0, 2, 4, 6, 8]
naive 24 comparisons, KMP 15 comparisons, same result: true
"xyz" in a text of 11 characters: found at []
naive 9 comparisons, KMP 13 comparisons, same result: true