KMP模板

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3+10,inf = 0x3f3f3f3f;
int nex[N]; //nex[j]的意思是当子串的第j个字符和主串的第i个字符不匹配时，我们应该从子串的nex[j]字符开始重新匹配 
string a,b;
/*
kmp指针回退 j = nex[j - 1]
根本原因：子串的指针j总是表示我们即将要匹配子串的第j个字符，所以如果子串[j]和主串[i]不匹配
那么我们自然是要从子串的nex[j - 1]字符开始重新匹配
*/
void get_next(string b)
{
    int j = 0; //前缀末尾
    for(int i = 1; i < b.size(); i++)
    {
        //指针回退
        while(j > 0 && b[i] != b[j]) j = nex[j - 1];
        //前缀和后缀的末尾相同则计数 
        if(b[j] == b[i]) j++;
        nex[i] = j; 
    } 
}
int kmp(string a,string b) //获取子串在主串中第一次出现的位置
{
    int j = 0; //子串指针j，主串指针i 
    for(int i = 0; i < a.size(); i++)
    {
        while(j > 0 && a[i] != b[j]) j = nex[j - 1]; //3.指针回退 
        if(a[i] == b[j]) j++; //1.当前子串和主串匹配，那么继续匹配子串的下一个 
        if(j == b.size()) //2.如果匹配完了，那么成功匹配的位置是：主串当前长度i - 子串长度b.size() + 1
        {
            //这里是返回子串在主串中第一次出现的位置，如果要解决其他问题，可以在这里进行修改 
            return i - b.size() + 1; 
        }
    }
    return -1; //没有匹配成功返回-1 
}
int main()
{
    getline(cin,a);
    getline(cin,b);
    get_next(b);
    cout << kmp(a,b);
    return 0;
}