KMP

KMP：字符串匹配。给你两个字符串，寻找其中一个字符串是否包含另一个字符串，如果包含，返回包含的起始位置。

#include<iostream>
//#include<cstring>
using namespace std;
int next[1000];
void NEXT(string b)
{
    //memset(next,-1,sizeof(int));
    int i,k=-1;
    next[0]=-1;
    for(i=1;i<b.size();i++)
    {
        while(k>-1&&b[k+1]!=b[i]) //这个while循环是KMP的重点
        k=next[k];
        if(b[k+1]==b[i]) k++;
        next[i]=k;
     }
}
int main()
{
    int i,k=-1,f;
    string a,b;
    while(cin>>a,a!="*")
    {
        f=-1;
        cin>>b; 
        NEXT(b);
        /*for(int i=0;i<b.size();i++)
        printf("%d
",next[i]);*/  //测试next
        //以下开始两个字符串比较
        for(i=0;i<a.size();i++)
        {
            while(k>-1&&b[k+1]!=a[i]) //这个while循环是KMP的重点 
            k=next[k];
            if(b[k+1]==a[i]) k++;
            if(k==b.size()-1) 
            {
                f=i-b.size()+1;
                break;
            }
        }
        printf("%d
",f);
    } 
}