KMP算法

KMP匹配相比较普通的匹配算法最坏情况为O(m*n)
KMP算法可以在O(m+n)的时间数量级上完成串的模式匹配操作。
主要思想在于打next表，用ij两指针相同则跳同时将next[i]=j不同则将j回溯j=next[j];
在主串查找也差不多ij两下标相同则跳不同则j回溯

#include<stdio.h>
#define maxstrlen 255
typedef unsigned char SString[maxstrlen+1];
void get_next(SString T,int next[]){
    //求串T的next函数值并存入数组next
    int i=1;
    next[1]=0;
    j=0;
    while(i<T[0]){
        if(j==0||T[i]==T[j]){
            i++;
            j++;
            next[i]=j;
        }else{
            j=next[j];
        }
    }
}
int index_kmp(SString S,SString T,int pos){
    //利用模式串T的next函数求T在主串中第pos个字符之后的位置.
    int i=pos,j=0;
    while(i<=S[0]&&j<=T[0]){
        if(S[i]==T[j]||j==0){
            i++;
            j++;
        }else{
            j=next[j];
        }
    }
    if(j>T[0])
        return i-T[0];
    else
        return 0;
}
int main{
    SString S;
}