[模板]kmp求Next数组

模板

#include <iostream>
#include <string>

using namespace std;

void getNext(const string& p,int next[])
{

    int len = (int)p.size();
    next[0] = -1;
    int k = -1;
    int j = 0;
    while(j < len - 1){
        if(k == -1 || p[j] == p[k]){
            j++;
            k++;
            next[j] = k;
        }else{
            k = next[k];
        }
    }
}

int main()
{
    string pattern;
    cin>>pattern;
    int patternLen = (int)pattern.size();
    int next[patternLen] = {0};
    getNext(pattern,next);
    for(int i=0;i<patternLen;i++){
        printf("%d ",next[i]);
    }
    return 0;
}