给定字符串$s$，试找出其最小真前缀$s_0$，

使得$s$可表示为若干$s_0$的拼接，或判断不存在这样的$s_0$。

设$s$的长度为$n$，$s[i]$的失配函数为$\pi[i]$。

结论：

1. $n-\pi[n] \mid n$则有$s_0=s[1][n-\pi[n]]$
2. $n-\pi[n] \nmid n$则$s_0$不存在

证明：

---

• 对于情况1.

---

若$s_0=s[1][k]$其中$k<n-\pi[n]$

则有$s[1][n-k]=s[k+1][n]$

此时$\pi'[n]=n-k>\pi[n]$矛盾

---

若$s_0=s[1][k]$其中$k=n-\pi[n]$

则有$s[1][n-k]=s[k+1][n]$于是

$s[1][k]=s[k+1][2k]=s[2k+1][3k]=...=s[n-2k+1][n-k]$

而$s_0=s[1][k]$，所以$s$可表示为若干$s_0$的拼接

---

若$s_0=s[1][k]$其中$k>n-\pi[n]$

因为$k>n-\pi[n]$所以此时$s_0$不是最短的，矛盾

---

综上，当$n-\pi[n] \mid n$时$s_0=s[1][n-\pi[n]]$

---

• 对于情况2.

---

若$\pi[n]<n-\pi[n]$且$s_0$存在

因为$s$至少为2个$s_0$的拼接，所以$n-\pi[n] \le n/2$

与假设矛盾。

---

若$\pi[n] \ge n-\pi[n]$且$s_0$存在，$s_0=s[1][k]$

显然$k \ge n-\pi[n]$否则$\pi'[n]=n-k>\pi[n]$矛盾

又$n-\pi[n] \nmid n$所以$k \ne n-\pi[n]$

即$k > n-\pi[n]$

设$w=n-\pi[n]$

可得$s_0=s[1][k]=s[w+1][w+k]=s[n-k+1][n]=s[n-w-k+1][n-w]$

因为$k > w$，所以$s[1][k]$和$s[w+1][w+k]$相交，$s[n-k+1][n]$和$s[n-w-k+1][n-w]$相交

所以$s_0[w+1][k]=s_0[1][k-w]$且$s_0[w+1][k]=s_0[1][w]$

$w \mid k$时由上式可得$s_0$能由若干$s_0[1][w]$拼接而成，矛盾

$w \nmid k$时设$l_0=k\%w$

由上式可得$s_0[1][l_0]=s_0[l_0+1][2l_0]=s_0[2l_0+1][3l_0]=...$

若$l_0 \mid k$则$s_0$能由若干$s_0[1][l_0]$拼接而成，矛盾

若$l_0 \nmid k$设$l_1=k\%l_0$有$s_0[1][l_1]=s_0[l_1+1][2l_1]=s_0[2l_1+1][3l_1]=...$

重复操作，由于序列$l$持续减少，必存在$l_x \mid k$，故$s_0$能由若干$s_0[1][l_x]$拼接而成，矛盾

---

综上，当$n-\pi[n] \nmid n$时不存在$s_0$

---

证毕。