KMP算法

#include <iostream>

using namespace std;


int *getNext(string pattern){
    int *next= (int *)malloc(sizeof(int)* pattern.size());

    if( next == NULL ){
        return NULL;
    }

    next[0] = -1;

    int j = -1;
    for( int i = 1; i < pattern.size(); i++ ){

        while(j != -1 && pattern[ j + 1 ] != pattern[i]){
            j = next[j];
        }

        if(pattern[j + 1] == pattern[i]){
            j++;
        }

        next[i]= j;
    }

    return next;

}

int kmpsearch(string texts, string pattern){
    int j;

    int *next = getNext(pattern);
    if(next == NULL){
        return -1;
    }

    j = 0;
    for (int i = 0; i < texts.size(); i++){

        while( j > 0 && pattern[j] != texts[i]){
            j = next[j -1] + 1;
        }

        if(pattern[j] == texts[i]){
            j++;
        }

        if(j == pattern.size() - 1){
            return i - j + 1;
        }
    }

    return -1;

}
int main(){
    int i;
    i = kmpsearch("abababc", "baba");

    cout<<i<<endl;
    return 0;
}