#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開(kāi)始，讓不匹配的回溯到開(kāi)始位置進(jìn)行匹配  
        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，或者當(dāng)前字符匹配成功（即S[i] == P[j]），都令i++，j++        
            if (j == -1 || s[i] == p[j])  
            {  
                i++;  
                j++;  
            }  
            else  
            {  
                //②如果j != -1，且當(dāng)前字符匹配失敗（即S[i] != P[j]），則令 i 不變，j = next[j]        
                //即通過(guò)next數(shù)組得到下次比較的位置     
                j = next[j];  
            }  
        }  
        delete []next;  
        if (j == pLen)//比較完畢而且比較了模式字符串的長(zhǎng)度表示找到匹配字符串  
            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])  
            {  
                //①如果當(dāng)前字符匹配成功（即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;  
    }  

標(biāo)簽：

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請(qǐng)與原作者聯(lián)系。