【day-12】KMP的next數組

#include <iostream>
#include <vector>
using namespace std;

vector<int> Next(string &partten){
    vector<int> next(partten.size());

    next[0]=-1;
    int k=-1;
    int i=0;
    while(i<partten.size()){
        if(k==-1 || partten[i]==partten[k]){
            next[++i]=++k;
        }else{
            k=next[k];
        }
    }
    return next;
}
/*-1 0 0 0 0 1 2 3 0 1 2 3 4*/
int main()
{
    string partten("ABCDABCEABCDG");
    auto res=Next(partten);
    auto it=res.begin();
    for(;it!=res.end();++it){
        cout<<*it<<" ";
    }
    cout<<endl;
    cout << "Hello world!" << endl;
    return 0;
}