In the Handbook of Exact String Matching algorithms, it describes the transition set for a basic string matching automaton as:


  • q in Q (q is a prefix of x)
  • a in $\Sigma$
  • (q, a, qa) is in E if and only if qa is also a prefix of x
  • otherwise (q, a, p) is in E such that p is the longest suffix of qa which is a prefix of x.

I'm having difficulty understanding the last statement. Why would there be a state transition to a suffix?


Assume that you build an automaton for finding occurrences of $bububa$ in the input string. When the automaton reads the input string $bubububa$, then it after reading $bububu$, it must not just return to state $\epsilon$, as otherwise an occurrence of $bububa$ is not detected. Also, jumping back to state $bu$ is would not do the trick, as then again, the $bububa$ starting in letter 3 of the word would be missed. Rather, after seeing a $u$ in state $bubub$, the automaton must transition to $bubu$ in order to no miss the possibility that only the first two letters are to be ignored.

The last line in the definition of $E$ describes how the back transitions in the automaton are found: in order not to miss any occurrence of $bububa$, the state in the automaton jumps back as little as possible.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.