資料結構面試之十四——字元串的模式比對

資料結構面試之十四——字元串的模式比對

題注：《面試寶典》有相關習題，但思路相對不清晰，排版有錯誤，作者對此參考相關書籍和自己觀點進行了重寫，供大家參考。

十四、字元串的模式比對

1.       模式比對定義——子串的定位操作稱為串的模式比對。

2.       普通字元串比對BF算法（Brute Force 算法，即蠻力算法）

【算法思想】：

第（1）步；從主串S的第pos個字元和模式的第一個字元進行比較之，若相等，則繼續逐個比較後續字元；否則從主串的下一個字元起再重新和模式串的字元比較之。

第（2）步驟；依次類推，直至模式T中的每一個字元依次和主串S中的一個連續的字元序列相等，則稱比對成功；函數值為和模式T中第一個字元相等的字元在主串S中的序号，否則稱為比對不成功，函數值為0。

比如對于主串S=”abacababc”; 模式串T=”abab”; 比對成功，傳回4。

對于主串S=”abcabcabaac”; 模式串T=”abab”; 比對不成功，傳回0。

【算法實作】：

//普通字元串比對算法的實作

int Index(char* strS, char* strT, int pos)

{  

     //傳回strT在strS中第pos個字元後出現的位置。

       int i = pos;

      int j = 0;

      int k = 0;

      int lens = strlen(strS);

      int lent = strlen(strT);

      while(i < lens && j < lent)

      {

             if(strS[i+k] == strT[j])

             {

                 ++j;    //模式串跳步

                    ++k;    //主串(内)跳步

               }

             else

             {

                 i = i+1;

                 j=0;  //指針回溯，下一個首位字元

                   k=0;

             }

      }//end i

       if(j >= lent)

         return i;

      }

      else

         return 0;

}//end

[算法時間複雜度]：設主串長度為m,模式串的長度為n。一般情況下n<m。

最好時間複雜度：舉例，主串S=”ababaababc”; 模式串T=”abab”; 比較次數為n次。時間複雜度為O（n）。

最壞時間複雜度：舉例，主串S=”000000000000000000001”（20個0，1個1）; 模式串T=”00001”（4個0，1個1）;比較次數為17*5次。時間複雜度接近O（m*n）。整個比對過程需要多次回溯（有16次回溯）。

平均時間複雜度：O(m*n)。

[空間複雜度]：O（1），不需要額外開辟空間存儲。

3.         KMP算法 ——是一種線性時間複雜的字元串比對算法，它是對BF算法改進。

[時間複雜度]：O(m+n)，即：O(strlen(S) + strlen(T))

[空間複雜度]：O(n)，即：O(strlen(T))

【核心思想】：是利用已經得到的部分比對資訊來進行後面的比對過程。

正文t

t1

t2

t3

tm

tn

模式p

p1

p2

p3

….

pm

.

【next（j）定義】:表示當pi不等于tr時，下一次将pnext[i] 與tr開始繼續後繼對應字元的比較。

其中next[0]=-1,表明當p0不等于tr時，将從p-1與tr開始繼續後繼對應字元的比較；顯然p-1是不存在的，我們可以将這種情況了解成下一步将從p0與tr+1開始繼續後繼對應字元的比較。

舉例說明1：模式串p=“google”,對應的next[j]={-1,0,0,0,1,0}。

解讀：

g

設定為-1

o

字元o之前沒有比對的字元。

字元o（第2個）之前的字元（g，o）不同。

字元g之前的字元（g，o，o）字首、字尾（如：g與o；go與oo）不比對。

l

字元l之前的字元（g，o，o，g）字首、字尾（如：g與g）相同，傳回1。

e

字元e之前的字元（g，o，o，g，l）字首、字尾（如：goo與ogl）不同。

舉例說明2：模式串p=“abaabcaba”，對應的next[j]={-1,0,0,1,1,2,0,1,2}。

【KMP算法實作】：

第一步：求解next數組。

typedef struct

{

      char str[100];

      int length;

}seqString;

//根據模式t的組成求其對應的next數組。

void getNext(seqString t, int next[])

     next[0] = -1;

      int i = 0;

      int j = -1;

      while(i < t.length)

             if(j == -1 || t.str[i] == t.str[j])

                    ++i;

                    ++j;

                    next[i] = j;

                    j = next[j];

      }//end while

      cout << "next[ "<< t.length << " ]" << endl;

      for(i = 0; i < t.length; i++)

             cout << next[i] << "\t";

     cout << endl;

第二步：KMP比對算法的實作。

//t代表正文源串，p代表模式比對串，next代表比對next數組

int kmp(seqString t, seqString p, int next[])

     while(i < t.length && j < t.length)

             if(j == -1 || t.str[i] == p.str[j])

                   i++;

                   j++;

                   j = next[j];

      if(j == p.length)

            return( i -p.length);

     {

             return -1;

}

int main()

      int rtnPos = 0;

      seqString strS;

      strcpy(strS.str,"goodgoogle");    //源串

   strS.length = strlen(strS.str);

      seqString strT;

      strcpy(strT.str,"abaabcaba");     //模式串

   strT.length = strlen(strT.str);

      int *pNext = new int[strT.length];

     getNext(strT,pNext);

      rtnPos = kmp(strS,strT,pNext);

      cout << rtnPos << endl;        //輸出比對位置

      return 0;

4.       手動示範BF算法與KMP算法的不同（如下圖所示）。

字元串的比對不是很好了解，JULY曾經用很長的篇幅去講，大家可以參考。很多材料講的思路一緻，但實作稍有差别，本文的實作和圖示是一緻的，有錯誤的話希望大家提出，不勝感激！