从kmp算法的正确性到rank_kmp

kmp算法

int p=nxt[0]=-1;
for(int i=1;i<=n;i++) {
    while(~p&&str[p+1]!=str[i]) p=nxt[p];
    nxt[i]=++p;
}

kmp 算法的正确性基于：

• 字符串相等具有传递性，即 $A=B,B=C\Rightarrow A=C$
• 两个字符串不相等，那么在后面加上一个字符后，两个串仍然不相等，即 $A\neq B \Rightarrow Ac\neq Bc$

而复杂度的瓶颈则是：

• 已知 $A=B$ ，判断 $Ac=Bc$ 是否成立

RANK-KMP

问题 (CEOI2011 Matching)

定义两个长度为$N$的序列$A$和$B$相似，当且仅当对于任意$i,j$，有$[ A_i < A_j ] = [ B_i < B_j ]$。给定序列$X,Y$，求$X$中有几个长度为$|Y|$的连续子序列和$Y$相似。$|X|,|Y|\le 10^6$。

Sol

对于一个字符串 $S$ ，定义 $fail_i$ 为 最大的 $x$ 使得 $S_{1\cdots x}$ 与 $S_{i-x+1\cdots i}$ 相似。

无论是求出 $fail$ 的过程，还是利用 $fail$ 进行字符串匹配的过程，我们实际上只需要解决这样一个问题：已知 $A$ 和 $B$ 相似，试判断 $Ac$ 和 $Bc$ 是否相似。

观察发现，只要 $c$ 在 $A$ 中的排名与 $c$ 在 $B$ 中的排名相同，$Ac$ 和 $Bc$ 就相似。可以随便用数据结构维护。

利用 $p$ 变化量线性的性质，可以得到一种优美的解法。