自写kmp算法。

#include<iostream>
#include<string>
#include<cmath>
#include<malloc.h>
using namespace std;
int Search_KMP(string,string,int*);
void nextval(string T,int len,int *);//len表示模式串T的长度，且模式串从0 
int main(void)
{
    string S,T;//S为主串，T为模式串 
    cout<<"请输入主串:";
    cin>>S;cout<<endl;
    cout<<"请输入模式串:";
    cin>>T;cout<<endl;
    int *next=(int *)malloc(sizeof(int)*S.length());next[0]=0;//存前缀和后缀的个数。 
    nextval(T,T.length(),next);
    Search_KMP(S,T,next);
    return 0;
}
int Search_KMP(string S,string T,int *next)
{
    int i=0,j=0;
    int len_s=S.length(),len_t=T.length();
    while(i<len_s&&j<len_t)
    {
        if(S[i]==T[j])
        {
            i++;
            j++; 
        }
        else
        {
              if(j!=0)
            {
                j=next[j-1];
            }
            else
            {
                i++;
            }  
        }
    }
    if(j==len_t)
    {
        cout<<"查找成功，位置为s串中的第:"<<i-j+1<<"位"<<endl;
    }
    else
    {
        cout<<"查找失败！"<<endl; 
    }
    
    
    
}
void nextval(string T,int len,int *next)
{

    int i=0,j=1,k=0;
    while(j<len)
    {
        if(T[i]!=T[j])
        {
            next[j]=0;
            j++;
        }
        else
        {
            next[j]=i+1;
            i++;j++;
            break;
        }
    }       
    //cout<<"asda"<<endl;
    while(j<len)
{
    int t=0;
    //cout<<"asdasdas"<<endl;
    if(T[i]!=T[j])
    {
        //cout<<"x"<<" "<<j<<endl;
        while(i!=0)
        {
            //cout<<"x"<<endl;
            i=next[i-1];
            if(T[i]==T[j])
            {
                //cout<<"asdasdasda"<<endl;
                next[j]=i+1;
                i++;j++;
                t=1;
                break;
            }
            //cout<<t<<endl;    
        }
        if(t==0)
        {
            //cout<<"y"<<endl;
            next[j]=0;
            j++;
        }
    }   
    else
    {
    //cout<<"z"<<endl;
    next[j]=i+1;
    i++;j++;
    }   
}   
}