思路

“KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的” by百度百科

kmp就是改进字符串匹配算法，利用匹配失败的信息减少枚举空间，确定下一个匹配将在哪里开始。不能白白失败，要从失败中汲取营养 ，把经验教训写在自己的“错题录”上 【自己白话理解】

所以需要错题录存储匹配失败后的有用信息 - next 数组

• next[i] = j 说明了 p[1 ~ j]前缀 和 p [i- j + 1 ~ i ]后缀 是匹配的
• 即为非平凡的最大后缀等于最大前缀

过程模拟

http://www.whocouldthat.be/visualizing-string-matching/

题目

给定一个模式串S，以及一个模板串P，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模板串P在模式串S中多次作为子串出现。
求出模板串P在模式串S中所有出现的位置的起始下标

样例

输入样例：

3
aba
5
ababa

输出样例：

0 2

暴力枚举 $o(n^2)$

//原串 ：s[N]   匹配模板串 ：P[M]

// 枚举匹配起点 看是否能匹配成功  【习惯从1开始 个人习惯】
for (int i = 1; i <= n; i ++ )
{
    bool flag = true;
    // 从起点开始枚举字符 逐一匹配 看是否都能匹配
    for (int j = 1; j <= m; j ++ )
        if (s[i + j - 1] != p[j]) // 出现不匹配的情况
        {
            flag=false; break;
        }
}

kmp $o(n+m)$ from 算法基础班

• next数组的初始化与计算
• 枚举主串起点 进行匹配，利用next[i]可以知道下一次从哪里开始匹配

#include <iostream>

using namespace std;

const int N = 10010, M = 100010;

int n, m;
// 非平凡的最大后缀等于最大前缀  | // next[] 可能会报错
int ne[N];   
char s[M], p[N];

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;  // 这样读入字符串下标从1开始

    // 计算next数组 ne[1] = 0;  p[1] 不能给前面退了
    for(int i = 2, j = 0; i <= n; i++)
    {
        while(j && p[i] != p[j + 1]) j = ne[j]; // 不匹配 退而求其次
        if(p[i] == p[j + 1]) j ++; // 成功 前进一步
        ne[i] = j;
    }


    // kmp匹配过程
    for(int i = 1, j = 0; i <= m; i++)
    {
        while(j && s[i] != p[j + 1]) j = ne[j]; // 不能匹配，我退一步 
        // while结束有两种情况 ：1）直到j 退无可退  2）匹配成功
        // 如果匹配
        if(s[i] == p[j + 1])  j++;
        if(j == n)
        {
          printf("%d ", i - n);
          j = ne[j]; // 
        }
    }

    return 0;
}