[算法]KMP 跳转数组实现

优化版

#include <iostream>
#define N 1000
using namespace std;
int nt[N];
void get_nt(string t){
    int k = -1;
    nt[0] = -1;
    int j = 0;
    while(j < t.length()){
        if( k== -1 || t[k]==t[j] ){
            k++; j++;
            if(t[k] == t[j]){
                nt[j] = nt[k]; 
            }else{
                nt[j] = k;
            }
        }else{
            k = nt[k];
        }
    }
}
int main(){
    string t = "aaaab";
    get_nt(t);
    for (int i = 0; i <= t.size(); i++)
    {
        cout << nt[i] << "  ";
    }

}

未优化版

#include <iostream>
using namespace std;
int ne[8];
void get_ne(string t){
    int k = -1;
    ne[0] = -1;
    int j =  0;
    while(j < t.length()){
        if(k == -1 || t[j] == t[k]){
            ne[++j] = ++k;
        }else{
            k = ne[k];
        }
    }
    
}

int main(){
//    abaabe
string t = "abaabe";
get_ne(t);
for (int i = 0; i <= t.size(); i++)
{
    cout << ne[i] << "  ";
}


}