My blog

博文链接

Record

一个重要的字符串算法，这是第三次复习。

通过总结我认为之所以某个算法总是忘记，是因为大脑始终没有认可这种算法的逻辑（也就是脑回路）。

本篇主要讲解从KMP的应用场景，再到算法知识，以及例题。

Main

现有两个字符串 $A, B$，求出 $A$ 在 $B$ 中出现的次数。
范围：字符串长度均 $\leq 1e6 + 10$。

其实简单来说，KMP就是优化了双重循环，解决字符串的匹配问题。

所以个人总结一下，遇到字符串的题目，如果dp用不了就考虑哈希和KMP

数学上从特殊到一般，那么这里我们从暴力到优化。

以 $A = abab , B = abababaaabb$ 为例，一般做法是双重循环，时间复杂度 $O(n ^ 2)$。

我们来看这个具体是怎么实现的。

每次枚举一个初始点，然后一位一位的判断是否相同。如果相同，就继续判断直到；如果不同，就退出并且选择下一个点作为初始点。

首先，如果说判断到第 $k$ 位发现不对，不是彻底无法挽救的。如果说这个子串从 $1 .. k - 1$ 的前缀和后缀都没有相同的，比如说这种 $abcfd$，那么判断过的位也不用再判断了，因为往后移一位就都错开了，所以就一直往后推，判断起点是否相同，相同就开始一位一位继续判断。如果说是这种 $abcabc$ 那就好办了，因为我们可以进行如下的操作。

abcabcbdde
abcabcd

这个时候再第七位发现有问题了，是不是全部跳过呢？当然不是。

abc|abcbdde
   |abcabcd

再从相同的前缀开始就可以了。只不过显然这个情况下还是匹配不了。

    for(int i = 1, j = 0; i <= m; i ++ )
    {
        while(j && b[i] != a[j + 1]) j = ne[j];
        if(b[i] == a[j + 1]) j ++ ;
        if(j == n)
        {
            cout << i - n << ' ';
            j = ne[j];
        }
    }

通过这样的思路，只需要每次遍历一遍母串，时间复杂度 $O(n)$。

在匹配之前，得要算一下子串中每一位对应的最长的前缀和后缀，记录下前缀的最后一位。

    for(int i = 2, j = 0; i <= n; i ++ )
    {
        while(j && a[i] != a[j + 1]) j = ne[j];
        if(a[i] == a[j + 1]) j ++ ;
        ne[i] = j;
    }

例题

周期

利用ne数组的性质，马上就可以得到一个字符串最长的相同前缀和后缀。观察发现，存在循环节的字符串观察可知：

• 当第 $i$ 位存在 $i \mod{(i - ne_i)} = 0$，那么他的循环节一定是 $i - ne_i + 1 … i$，个数是 $i / (i - ne_i)$。

这个自己打打草稿就出来了，不多说了。

代码