acwing算法基础课：kmp

KMP 模板

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}

例题

求出模板串P在模式串S中所有出现的位置的起始下标。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 10010, M = 1010;

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

int main()
{
    //s模式串， p匹配串
    cin >> n >> s + 1 >> m >> p + 1;

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

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

    return 0;
}

测试样例

输入样例
5
ababa
3
aba
输出样例
1 3