[AcWing]831. KMP字符串（C++实现）KMP模板题

[AcWing]831. KMP字符串（C++实现）KMP模板题

[AcWing]831. KMP字符串（C++实现）KMP模板题

• 1. 题目
• 2. 读题（需要重点注意的东西）
• 3. 解法
• 4. 可能有帮助的前置习题
• 5. 所用到的数据结构与算法思想
• 6. 总结

1. 题目

2. 读题（需要重点注意的东西）

思路：KMP的主要思路是如何通过已经比较的数，来减少两个字符串比较的次数。

接下来我会分析为什么可以减少比较的次数，这就是KMP的核心思想。

比较难以理解的地方就在于跳转的 *** 作，这个 *** 作只与p串本身有关，而与s串无关

跳转的 *** 作本质上是一个求最大的相同前后缀长度的过程，每个字符串最大的相同前后缀长度即为p[i]不匹配时为跳
转的地方，如p串为ababab时（下标从1开始）：

ne[1] = 0; 
ne[2] = 0;  最大的前缀为a，后缀为b
ne[3] = 1;  前缀为ab，后缀为ba时不等；前缀为a，后缀为a时相等，因此最大的相同前后缀长度为1
ne[4] = 2;  前缀为aba，后缀为bab时不等；前缀为ab，后缀为ab时相等，因此最大的相同前后缀长度为2

同理：

ne[5] = 3;
ne[6] = 4;

那么为什么求每个位置最大相同前后缀长度能减少比较次数呢？

我们看这样一种情况：（整个过程的视频演示在后面）
当比较到这样一种情况时：s[i] 与 p[j+1]不等了 ( 此时j=5 )

执行跳转 *** 作，j = ne[5] = 3 ，相当于整个p串向后移动了
再比较 s[i] 和 p[j+1 = 4]的大小

我们可以看到，跳转后，绿色框中的值天生就是是完全相同的，不用再比较了
此时也只需要比较一位数即可，不用重新全部比较一遍
还是不同，再根据j = ne[3] = 1 跳转；比较s[i] 和 p[ j+1 = 2 ]

比较此时的s[i] 和 p[j+1]的大小，又失败了，那么直到跳转到j = 0，说明比较失败。

i此时再向前移动一位进行比较

---------------------------整个跳转过程的视频演示-------------------------------------

---

发现了吗？

i 只有当 ne 全部跳转完时，才会继续走到下一位进行比较。因此，只需要遍历一遍s串，就能够知道p串是否能匹配s串的子串。

这样，仅仅通过跳转，就减少了字符串比较的次数。

3. 解法

---------------------------------------------------解法---------------------------------------------------

#include 

using namespace std;

const int N = 100010, M = 1000010;

int n, m;
int ne[N];
char s[M], p[N];

int main()
{
    // ----------------输入开始--------------------------
    // cin >> n >> p+1 >> m >> s+1; 
    // 相当于以下四句代码
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> p[i];
    cin >> m;
    for(int i = 1;i <= m;i++) cin >> s[i];
    // ----------------输入结束--------------------------
    
    // 构建ne数组,表示匹配不成功时可以直接向后跳多少位
    for (int i = 2, j = 0; i <= n; i ++ )
    {
        // 如果j不为0，且当前值不匹配，j跳转到ne[j]
        // p[i]前面的值可以不用比较，只需要比较p[i]和p[j+1]，想想为什么？---KMP的核心
        while (j && p[i] != p[j + 1]) j = ne[j];
        // 如果当前值匹配，则可以继续匹配下一个值 i++ 和 j++
        if (p[i] == p[j + 1]) j ++ ;
        // 不匹配了，j此时是最大的前缀后缀相等的长度，将其赋值给ne[i]，最大长度就是跳转的位置
        ne[i] = j;
    }
    
    // 匹配字符串
    for (int i = 1, j = 0; i <= m; i ++ )
    {
        // 如果j不为0，且当前s的值s[i]与当前p的值p[j+1]不匹配，j直接跳到到ne[j] 
        while (j && s[i] != p[j + 1]) j = ne[j];
        // 如果当前值匹配，继续匹配下一个值 j++
        if (s[i] == p[j + 1]) j ++ ;
        // 匹配成功
        if (j == n) printf("%d ", i - n);
    }

    return 0;
}

4. 可能有帮助的前置习题 5. 所用到的数据结构与算法思想 6. 总结

KMP算法模板题，推荐完全背下来。