字符串匹配的算法（暴力算法和KMP算法）

    #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;  
}  </pre>