字符串算法三连击

本文是介绍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.