KMP

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
#include<map>
using namespace std;

int next[1000];

void GetNext(string a)
{
    memset(next,0,sizeof(next));
    int j,k;
    j=0;k=-1;
    next[0]=-1;
    while(j<a.length()-1)
    {
        if(k==-1||a[j]==a[k])
        {
            j++;k++;
            if(a[j]!=a[k])
                next[j]=k;
            else
                next[j]=next[k];
        }
        else k=next[k];
    }
}

int KMP(string a,string b)
{
    GetNext(b);
    int i=0,j=0,t=0;
    while(i<a.length()&&j<(int)b.length())//注意b.length()是unsignint型会产生-1>b.length()的错误 
    {
        if(j==-1||a[i]==b[j])
        {
            i++;j++;
        }
        else
        {
            j=next[j];
        }
    }
    if(j>=b.length())
        return(i-b.length());
    else
        return -1;
}

int main()
{
    string a="aaasdasasdaasaaaaaaaaaabsdaihgwudiqgifajsgfi";
    string b="aaaab";
    cout<<KMP(a,b)<<endl;
    return 0;
}