Question 10.2.3: as we said, the difficulty appears because there are several......
as we said, the difficulty appears because there are several possible positions of the pattern; each position corresponds to some prefix of the pattern that is also a suffix of the input string. The finite automaton remembers only the longest one. What about others?
The longest prefix-suffix X determines all other prefix-suffixes.
Namely, prefix-suffixes of the processed part are prefixes of X that are also suffixes of X.
It is easy to write a transition table and a program for any fixed pattern. How-ever, we want to write a general program that will search for any given pattern in any given input string. The following approach may be used. Consider a program that has two stages. In the first stage, it examines the pattern and constructs a transition table for that pattern. In the second stage, it reads the input string and behaves according to the transition table. Such an approach is often used for more complicated patterns (see below), but for substring search there is more direct and
efficient method called Knuth-Morris-Pratt algorithm. (A similar approach was suggested by Yu. Matijasevich.) We start with some auxiliary lemmas.