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?

Step-by-Step

Learn more on how do we answer questions.

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.

Question: 10.2.1

A problem arises when the pattern contains repetit...

Question: 10.7.13

For the deterministic finite automata the transiti...

Question: 10.7.11

Assume that the nondeterministic automaton has ver...

Question: 10.7.12

In the Floyd algorithm for the shortest path (see ...

Question: 10.7.10

The states of the deterministic automaton are sets...

Question: 10.7.9

This automaton is constructed inductively, followi...

Question: 10.7.7

((a\mid b\mid c \mid d\mid e)\ast a (a\mid...

Question: 10.7.8

To prove this, we need the notion of a nondetermin...

Question: 10.7.6

((a\mid b\mid c)\ast bac (a \mid b \mid c)...

Question: 10.7.5

The expression b∗ defines the set of all strings w...