字符串-前缀函数与KMP

Skyzhou666 · 2024-09-12 14:32:18 · 算法·理论

前缀函数与KMP

模版

#include <iostream>
#include <vector>
#define MAXN 2000001
using namespace std;

int ans2[MAXN];

vector <int> prefix(string s) //前缀函数
{
    int n = s.length();
    vector <int> pi(n);
    for(int x = 1; x < n; x++)
    {
        int y = pi[x-1];
        while(y > 0 && s[x] != s[y]) y = pi[y-1];
        if(s[x] == s[y]) y++;
        pi[x] = y;
    }
    return pi;
}

vector <int> find_str(string s1, string s2) //KMP算法核心
{
    string cur = s2 + '#' + s1;
    int l1 = s1.size(), l2 = s2.size();
    vector <int> v;
    vector <int> lps = prefix(cur);
    for(int x = 0; x < lps.size(); x++) ans2[x] = lps[x];
    for(int x = l2+1; x <= l1+l2; x++)
        if(lps[x] == l2) v.push_back(x - 2*l2);
    return v;
}

int main()
{
    string s1, s2;
    cin >> s1 >> s2;
    vector <int> ans = find_str(s1, s2);
    for(int x = 0; x < ans.size(); x++) cout << ans[x]+1 << endl;
    for(int x = 0; x < s2.length(); x++) cout << ans2[x] << " ";
    cout << endl;
    return 0;
}

OI-WIKI