KMP模板

kmp模板：

//得到next数组
void get_next(string s,int& next)
{
    int i=0;
    int j=-1;
    next[i]=j;
    int len=s.length();
    while(i<len){
        if(j==-1||s[i]==s[j]){
            ++i;
            ++j;
            //未优化
            next[i]=j;
            //优化
            if(s[i]==s[j])
                 next[i]=next[j];
            else
                next[i]=j;
        }
    }
}
//kmp
//返回第一个位置
void kmp(string S,string T,int &pos)
{
    int len1=S.length();
    int len2=T.length();
    int i,j;
    i=j=0;
    int next[100000];
    get_next(T,next);
    while(i<len1&&j<len2){
        if(j==-1||S[i]==T[j]){
            ++i;
            ++j
        }
        else
            next[j]=j;
    }
    if(j==len2)
        pos=i-j;
    else 
        pos=-1;
    return ;
}