字符串算法三连击

本文是介绍KMP算法的运用

KMP算法

给定两个字符串 ，询问 是否在 中出现过，如果出现过要给出所有出现的位置，时间复杂度

KMP算法的核心是Next数组

Next 数组

定义 : 函数，它表示一个字符串的最长的严格前缀等于对应长度后缀的长度

，因为前缀和后缀都是 ，并且没有更长的了

，因为前缀和后缀都是 ，注意原串 也同时是前缀和后缀，但我们要求是严格前缀

，因为不存在一个前缀等于对应长度后缀

对于一个字符串 ，我们定义它的 数组的第 项为 前 个字符构成的前缀的 函数
对于字符串 来说，它的 数组是：

算法主体

如果要求 是否在 中出现过，先求 的 数组（假设已经求好）

记录两个指针 ，表示当前匹配到字符串 的位置，匹配到字符串 的 位置

如果 ，该字符匹配成功，

如果 ，匹配失败， （ 移动到可行的最后一个位置）

如果 到末尾，说明已经匹配成功，输出匹配位置，并，表示开始准备下一次匹配

求Next数组

核心思想：自己与自己错位做匹配

考虑已知 ，求

如果 ，那么
如果不相等？判断

for (int i = 2; i <= length; i++) {
    while (j > 0 && S[i] != S[j + 1]) j = next[j];
    if (S[i] == S[j+1]) j++;
    next[i] = j;
}

KMP在题目中的应用

下面是一些的题目

周期串判断

题目

给定一个字符串 ，问 是否是周期串，也就是是否有 这样的形式。如果有找出最短的循环节，否则输出 。

题解

考虑周期串有什么性质：如果 （ 个 连在一起），那么 既是 的前缀也是 的后缀，也就是 的长度应该等于

如果 是 的一个约数的话，根据前缀后缀的相等关系我们可以断定 必然是周期串，又由于 的最大性质，前 个字符一定就是最短循环节。否则 必然不是一个周期串。

CEOI 2011 Match

题目

给出一个长度为 的排列 （ 到 的所有数都出现一次），并给出一个长度为 的序列 ，求 的所有满足如下条件的子串：

• 该子串长度为
• 该子串的第 个数恰为整个子串的第 大的数

题解

修改一下 KMP 算法中， 中等号的定义.

定义 是 在 的前 位中的排名。
如果 的某个子串 中， 的排名恰好是 ，就认为。

可以用树状数组在将 离散化后 判定。

Q: 为什么这样做是对的呢？

考虑当前匹配的指针后移一位，不会影响之前的匹配结果

实际上就是把排名对应相等的字符串看成是等价的字符串做匹配

End.