# Connection between KMP prefix function and string matching automaton

Let $A_P = (Q,\Sigma,\delta,0,\{m\})$ the string matching automaton for pattern $P \in \Sigma^m$, that is

• $Q = \{0,1,\dots,m\}$
• $\delta(q,a) = \sigma_P(P_{0,q}\cdot a)$ for all $q\in Q$ and $a\in \Sigma$

with $\sigma_P(w)$ the length of the longest prefix of $P$ that is a Suffix of $w$, that is

$\qquad \displaystyle \sigma_P(w) = \max \left\{k \in \mathbb{N}_0 \mid P_{0,k} \sqsupset w \right\}$.

Now, let $\pi$ the prefix function from the Knuth-Morris-Pratt algorithm, that is

$\qquad \displaystyle \pi_P(q)= \max \{k \mid k < q \wedge P_{0,k} \sqsupset P_{0,q}\}$.

As it turns out, one can use $\pi_P$ to compute $\delta$ quickly; the central observation is:

Assume above notions and $a \in \Sigma$. For $q \in \{0,\dots,m\}$ with $q = m$ or $P_{q+1} \neq a$, it holds that

$\qquad \displaystyle \delta(q,a) = \delta(\pi_P(q),a)$

But how can I prove this?

For reference, this is how you compute $\pi_P$:

m ← length[P ]
π[0] ← 0
k ← 0
for q ← 1 to m − 1 do
while k > 0 and P [k + 1] =6 P [q] do
k ← π[k]
if P [k + 1] = P [q] then
k ← k + 1
end if
π[q] ← k
end while
end for

return π

-
Can you provide a little more detail? What is the pattern? What precisely is the prefix function -- I didn't see a prefix function on the link you provided? Is the automaton deterministic or nondeterministic? –  Dave Clarke May 5 '12 at 10:35
Isn't that the definition of the KMP transition function? You might find these notes helpful (but see footnote 1). –  JeffE May 6 '12 at 15:25
I edited the question with the prefix function of KMP –  Bob May 7 '12 at 8:20
So, your question is basically how to prove that the code above computes the prefix function of KMP. –  rgrig May 7 '12 at 14:31
@Raphael: I find the edited question much less readable. –  JeffE May 16 '12 at 2:55

First of all, note that by definition

• $\delta(q,a) = \sigma_P(P_{0,q}\cdot a) =: s_1$ and
• $\delta(\pi_P(q),a) = \sigma_P(P_{0,\pi_P(q)}\cdot a) =: s_2$.

Let us investigate $s_1$ and $s_2$ in a sketch:

[source]

Now assume $s_2 > s_1$; this contradicts the maximal choice of $s_1$ directly. If we assume $s_1 > s_2$ we contradict the fact that both $s_2$ and $\pi_P(q)$ are chosen maximally, in particular because $\pi_P(q) \geq s_1 - 1$. As both cases cases lead to contradictions $s_1=s_2$ holds, q.e.d.

As requested, a more elaborate version of the proof:

Now we have to show $s_1=s_2$; we do this by showing that the opposite leads to contradictions.

• Assume $s_2 > s_1$. Note that $P_{0,s_2} \sqsupset P_{0,q}\cdot a$ because $P_{0,s_2} \sqsupset P_{0,\pi_P(q)}\cdot a$ and $P_{0,\pi_P(q)} \sqsupset P_{0,q}$ by definition of $s_2$. Therefore, $P_{0,s_2}$ -- a prefix of $P$ and a suffix of $P_{0,q}\cdot a$ -- is longer than $P_{0,s_1}$, which is by definition of $s_1$ the longest prefix of $P$ that is a suffix of $P_{0,q}\cdot a$. This is a contradiction.

Before we continue with the other case, let us see that $\pi_P(q) \geq s_1 - 1$. Observe that because $P_{0,s_1} \sqsupset P_{0,q}\cdot a$, we have $P_{0,s-1} \sqsupset P_{0,q}$. Assuming that $\pi_P(q) < s_1 - 1$ immediately contradicts the maximal choice of $\pi_P(q)$ ($s_1 - 1$ is in the set $\pi_P(q)$ is chosen from).

• Assume $s_1 > s_2$. We have just shown $|P_{0,\pi_P(q)}\cdot a| \geq s_1$, and remember that $P_{0,\pi_P(q)}\cdot a \sqsupset P_{0,q} \cdot a$. Therefore, $s_1 > s_2$ contradicts the maximal choice of $s_2$ ($s_1$ is in the set $s_2$ is chosen from).

As neither $s_1 > s_2$ nor $s_2 > s_1$ can hold, we have proven that $s_1 = s_2$, q.e.d.

-
I think that is correct, but can you give me a formal prof of contradictions? I want to understand why this is correct –  Bob May 26 '12 at 7:27
@Bob: This is just a textualisation of what was there before + sketch + some thinking, but there you go. If you have trouble still, I suggest you redraw the sketch assuming $s_2\neq s_1$ (in either direction); you can then read off the contradiction, literally. –  Raphael May 26 '12 at 9:23
Thanks a lot! :) –  Bob May 26 '12 at 9:50
Just another thing. In the second step of the proof, we have $|P_{0,\pi_P(q)}\cdot a| \geq s_1$. My question is why $P_{0,\pi_P(q)}\cdot a$ in abs? –  Bob Jun 8 '12 at 8:01
@Bob: $|.|$ is the length of the string. –  Raphael Jun 8 '12 at 10:58