字元串查找算法BF和KMP

其中，Target為主串，Pattern為子串（模式串），如果在主串Target的第pos個位置後存在與子串Pattern相同的子串，傳回它在主串Target中第pos個字元後第一次出現的位置，否則傳回-1

1、 BF算法(Brute-Force，最基本的字元串比對算法)

int BF(const string &Target,const string &Pattern,int pos)  
{  
    int i = pos;  //主串目前正待比較的位置，初始為pos  
    int j = ;   //子串目前正待比較的位置，初始為0  
    int Tlen = Target.size();  //主串長度  
    int Plen = Pattern.size();  //子串長度  

    while(i < Tlen && j < Plen)  
    {  
        if(Target[i] == Pattern[j])   //如果目前字元相同，則繼續向下比較  
        {     
            i++;  
            j++;  
        }  
        else   //如果目前字元不同，則i和j回退，重新進行比對  
        {     
            i = i-j+;  //Target退回下一輪開始比較的位置     
            j = ;  //Pattern退回到子串開始處
        }  
    }  

    if(j >= Plen)  
        return i - Plen;  //傳回比對第一個位置
    else  
        return -;  
}  
           

2、KMP

上述算法的時間複雜度之是以大，是由于索引指針的回溯引起的，針對以上不足，便有了KMP算法。KMP算法可以在O（Plen+Tlen）的時間數量級上完成串的模式比對操作。其改進之處在于：每一趟比較重出現字元不等時，不需要回溯索引指針i，而是利用已經得到的部分比對的結果将子串向右滑動盡可能遠的距離，繼續進行比較。它的時間複雜度為O（Plen+Tlen），空間複雜度為O（Plen）

KMP算法的關鍵是利用比對失敗後的資訊（已經比對的部分中的對稱資訊），盡量減少模式串（待搜尋詞）與文本串的比對次數以達到快速比對的目的。具體實作就是實作一個next()函數，該函數本身包含了模式串的局部比對資訊。

void GetNext(const string &Pattern,int next[],int len)  
{  
    int j = ;  
    int k = -;  
    next[] = -;  

    while(j < len-)  
    {  //p[k]表示字首，p[j]表示字尾  
        if(k == - || Pattern[j] == Pattern[k])  
        {   //如果滿足上面分析的Pk = Pj的情況，則繼續比較下一個字元，  
            //并得next[j+1]=next[j]+1  
            j++;  
            k++;  
            next[j] = k;  
        }  
        else  
        {   //如果符合上面分析的第2種情況，則依據next[k]繼續尋找下一個比較的位置  
            k = next[k];  
        }  
    }  
}  
           

int KMP(const string &Target,const string &Pattern,int pos,int next[])  
{  
    int i = pos;  //主串目前正待比較的位置，初始為pos  
    int j = ;   //子串目前正待比較的位置，初始為0  
    int Tlen = Target.size();  //主串長度  
    int Plen = Pattern.size();  //子串長度  

    while(i < Tlen && j < Plen)  
    {  
        if(j==- || Target[i] == Pattern[j])     
        {       //如果目前字元相同，或者在子串的第一個字元處失配，則繼續向下比較  
            i++;  
            j++;    
        }  
        else   //如果目前字元不同，則i保持不變，j變為下一個開始比較的位置  
        {     
            //next數組是KMP算法的關鍵，i不回退，  
            //而是繼續與子串中的nex[j]位置的字元進行比較  
            j = next[j];  
        }  
    }  

    if(j >= Plen)  
        return i - Plen;  
    else  
        return -;  
}