#include<iostream>  
    #include<string>  
    using namespace std;  
    int KMPfind(char* s, char* p);  
    void GetNext(char* p, int next[]);  
    int ViolentMatch(char* s, char* p);  
    int main()  
    {  
        char s1[] = "abcaabbaacaadaabbaa";  
        char s2[] = "aadaab";  
        cout << "In the string " << s1 << ", the string " << s2 << " is started at the "  
            << ViolentMatch(s1, s2);  
        cout << endl<<KMPfind(s1, s2)<<endl;  
        return 0;  
    }  
    void GetNext(char* p, int next[])  
    {  
        int pLen = strlen(p);  
        int i = -1; int j = 0;//i从-1开始，让不匹配的回溯到开始位置进行匹配  
        next[0] = -1;//  
        for (; j < pLen-1;)  
        {  
            if (i==-1||p[i] == p[j])  
            {  
                ++i; ++j; next[j] = i;  
            }  
            else  
                i = next[i];//i回溯到next[i]的位置  
        }  
          
    }  
    int KMPfind(char* s, char* p)  
    {  
        int i = 0;  
        int j = 0;  
        int sLen = strlen(s);  
        int pLen = strlen(p);  
        int * next = new int[strlen(p)];  
        GetNext( p,  next);  
        while (i < sLen && j < pLen)  
        {  
            //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++        
            if (j == -1 || s[i] == p[j])  
            {  
                i++;  
                j++;  
            }  
            else  
            {  
                //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]        
                //即通过next数组得到下次比较的位置     
                j = next[j];  
            }  
        }  
        delete []next;  
        if (j == pLen)//比较完毕而且比较了模式字符串的长度表示找到匹配字符串  
            return i - j;  
        else  
            return -1;  
    }  
    int ViolentMatch(char* s, char* p)  
    {  
        int sLen = strlen(s);  
        int pLen = strlen(p);  
      
        int i = 0;  
        int j = 0;  
        while (i < sLen && j < pLen)  
        {  
            if (s[i] == p[j])  
            {  
                //①如果当前字符匹配成功（即S[i] == P[j]），则i++，j++        
                i++;  
                j++;  
            }  
            else  
            {  
                //②如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0        
                i = i - j + 1;  
                j = 0;  
            }  
        }  
        //匹配成功，返回模式串p在文本串s中的位置，否则返回-1    
        if (j == pLen)  
            return i - j;  
        else  
            return -1;  
    }