算法｜KMP算法

const int MAXN = 1000;
const int MAXM = 10000;

int nextTable[MAXN];
int pattern[MAXN];
int text[MAXM];

void getNextTable(int n){
    int i = -1;  // 前缀末尾
    int j = 0;  // 后缀末尾
    nextTable[0]=-1;
    while(j<n){
        if(i==-1 || pattern[i]==pattern[j] ){
            i++;
            j++;
            nextTable[j] = i;
        }
        else
            i=nextTable[i];  // 后缀的位置回退
    }
    return;
}

int KMP(int n, int m){
    getNextTable(n);  //初始化next数组
    int i = 0,j=0;  // i为pattern的指针 j为text的指针
    while(i<n && j < m){
        if(i==-1||pattern[i]==text[j]){
            i++;
            j++;
        }
        else
            i=nextTable[i];  // pattern回退
    }
    if(i==n)  // 模式串匹配结束
        return j-i+1;
    else
        return -1;
    
}