KMP

1 P3375 【模板】KMP - 洛谷

#include <bits/stdc++.h>
using namespace std;
string s1, s2;
int ne[1000010];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cin >> s1 >> s2;
    // ne[0] = 0;
    for (int i = 1, j = 0; i < s2.length(); ++i)
    {
        while (j && s2[i] != s2[j])
            j = ne[j - 1];
        if (s2[i] == s2[j])
            j++;
        ne[i] = j;
    }
    for (int i = 0, j = 0; i < s1.length(); ++i)
    {
        while (j && s1[i] != s2[j])
            j = ne[j - 1]; // 不断前移j指针，直到成功匹配或移到头为止
        if (s1[i] == s2[j])
            j++; // 当前位匹配成功，j指针右移
        if (j == s2.length())
        {
            cout << i - j + 2 << '\n'; //输出对应匹配的位置
            // 对s1[i - j + 1 .. i]进行一些操作
            j = ne[j - 1];
        }
    }
    for (int i = 0; i < s2.length(); i++)
        cout << ne[i] << ' ';
}