【模板】KMP

合并在一起求

#include <bits/stdc++.h>
using namespace std;
string s1, s2;
string t;
int nxt[2000000 + 5];
void gen_nxt(const string &t)
{
    nxt[0] = 0;
    for (int i = 1; i < t.length(); i++)
    {
        int j = nxt[i - 1];
        while (j && t[i] != t[j])
            j = nxt[j - 1];
        if (t[i] == t[j])
            j++;
        nxt[i] = j;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s1 >> s2;
    t = s2 + "#" + s1;
    gen_nxt(t);
    /*
    for (int i = 0; i < t.size(); i++)
        cout << t[i] << " ";
    cout << "\n";
    for (int i = 0; i < t.size(); i++)
        cout << nxt[i] << " ";
    cout << "\n";
    */
    for (int i = 0; i < t.size(); i++)
        if (nxt[i] == s2.size())
            cout << i - s2.size() - s2.size() + 1 << "\n";
    for (int i = 0; i < s2.size(); i++)
        cout << nxt[i] << " ";
    return 0;
}

/*
0 1 2 3 4 5 6
A B A # A B A B A B C
0 0 1 0 1 2 3 2 3 2 0
*/

分离分别求（一般不常用）

#include <bits/stdc++.h>
using namespace std;
string s1, s2;
// p: 模式串、t：文本串
// 在文本中去找到所有和模式匹配的位置
int nxtP[2000000 + 5];
int nxtT[2000000 + 5];
void gen_nxt(const string &p, const string &t)
{
    // 先对模式串本身求 nxtP
    nxtP[0] = 0;
    for (int i = 1; i < p.length(); i++)
    {
        int j = nxtP[i - 1];
        while (j && p[i] != p[j])
            j = nxtP[j - 1];
        if (p[i] == p[j])
            j++;
        nxtP[i] = j;
    }
    // 求 nxtT
    if (t[0] == p[0])
        nxtT[0] = 1;
    else
        nxtT[0] = 0;
    for (int i = 1; i < t.length(); i++)
    {
        int j = nxtT[i - 1];
        while (j && (j == p.size() || t[i] != p[j]))
            j = nxtP[j - 1];
        if (t[i] == p[j])
            j++;
        nxtT[i] = j;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s1 >> s2;
    gen_nxt(s2, s1);
    for (int i = 0; i < s1.size(); i++)
        if (nxtT[i] == s2.size())
            cout << i - s2.size() + 2 << "\n";
    for (int i = 0; i < s2.size(); i++)
        cout << nxtP[i] << " ";
    return 0;
}

/*
0 1 2 3 4 5 6
A B A # A B A B A B C
0 0 1 0 1 2 3 2 3 2 0
*/

求模式串的，然后在文本串中匹配（常用）

#include <bits/stdc++.h>
using namespace std;
string s1, s2;
// 求模式串 s2 的 nxt
int nxt[1000000 + 5];
void gen_nxt(const string &t)
{
    nxt[0] = 0;
    for (int i = 1; i < t.length(); i++)
    {
        int j = nxt[i - 1];
        while (j && t[i] != t[j])
            j = nxt[j - 1];
        if (t[i] == t[j])
            j++;
        nxt[i] = j;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s1 >> s2;
    gen_nxt(s2);
    int last = 0;
    for (int i = 0; i < s1.size(); i++)
    {
        while (last && s1[i] != s2[last])
            last = nxt[last - 1];
        if (s1[i] == s2[last])
            last++;
        if (last == s2.size())
            cout << i - s2.size() + 2 << "\n";
    }
    for (int i = 0; i < s2.size(); i++)
        cout << nxt[i] << " ";
    return 0;
}

/*
0 1 2 3 4 5 6
A B A # A B A B A B C
0 0 1 0 1 2 3 2 3 2 0
*/