KMP前缀函数与匹配自动机的字符串之间的连接

Question

令$ a_p =（q， sigma， delta，0， {m }）$ the 字符串匹配自动机 对于 sigma^m $中的图案$ p ，也就是说

• $ q = {0,1， dots，m } $
• $ delta（q，a）= sigma_p（p_ {0，q} cdot a）$ in q $中的所有$ q in in sigma $

带有$ sigma_p（w）$的最长前缀$ p $的长度为$ w $，即

$ qquad displayStyle sigma_p（w）= max left {k in mathbb {n} _0 mid p_ {0，k} sqsupset w right } $。

现在，让$ pi $ 前缀功能 来自 Knuth-Morris-Pratt算法, ， 那是

$ qquad displaystyle pi_p（q）= max {k mid k <q wedge p_ {0，k} sqsupset p_ {0，q} } $。

事实证明，可以使用$ pi_p $快速计算$ delta $；中心观察是：

假设上述概念和 sigma $中的$ a 。对于$ q in {0， dots，m } $，带有$ q = m $或$ p_ {q+1} neq a $，它认为

$ qquad displaystyle delta（q，a）= delta（ pi_p（q），a）$

但是我该如何证明这一点呢？

---

作为参考，这是您计算$ 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 π

Answer 1

首先，请注意，根据定义

• $ 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 $。

让我们在草图中调查$ s_1 $和$ s_2 $：

^[资源]

现在假设$ S_2> S_1 $;这与直接的$ S_1 $的最大选择相矛盾。如果我们假设$ s_1> s_2 $，我们与以下事实相矛盾。 两个都 $ s_2 $和$ pi_p（q）$是最大选择的，特别是因为$ pi_p（q） geq s_1-1 $。由于两种情况都导致矛盾$ s_1 = s_2 $保持，QED

---

根据要求，更精细的证明版本：

现在我们必须显示$ S_1 = S_2 $;我们通过证明相反的导致矛盾来做到这一点。

• 假设$ S_2> S_1 $。请注意，$ p_ {0，s_2} sqsupset p_ {0，q} cdot a $因为$ p_ {0，s_2} sqsupset p_ {0， pi_p（q）} ， pi_p（q）} sqsupset p_ {0，q} $按$ s_2 $的定义。因此，$ p_ {0，s_2} $ - $ p $的前缀 和 $ p_ {0，q} cdot a $的后缀 更长 比$ p_ {0，s_1} $，它是$ s_1 $的定义，是$ p $的最长前缀，是$ p_ {0，q} cdot a $的后缀。这是一个矛盾。

在继续另一种情况之前，让我们看看$ pi_p（q） geq s_1-1 $。观察，因为$ p_ {0，s_1} sqsupset p_ {0，q} cdot a $，我们有$ p_ {0，s-1} sqsupset p_ {0，q} $。假设$ pi_p（q）<s_1-1 $立即与$ pi_p（q）$的最大选择相矛盾（$ s_1-1-1 $是在集合$ pi_p（q）$中选择的）。

• 假设$ S_1> S_2 $。我们刚刚显示$ | p_ {0， pi_p（q）} cdot a | geq s_1 $，请记住$ p_ {0， pi_p（q）} cdot a sqsupset p_ {0，q} cdot a $。因此，$ s_1> s_2 $与$ s_2 $的最大选择相矛盾（$ s_1 $是在set $ s_2 $中选择的）。

由于$ s_1> s_2 $也不是$ s_2> s_1 $可以保持，我们已经证明$ s_1 = s_2 $，Qed