大話數據結構之四（串） @ 互聯網

文章出處

串的定義

串是由零個或多個字符組成的有限序列，又名叫字符串

串中的字符數目n稱為串的長度

零個字符的串稱為空串

串的抽象數據類型

串的順序存儲結構

串我鏈式存儲結構

一個結點可以存儲一個字符也可以考慮存儲多個字符，最后一個結點若是未被占滿時，可以用#或其它非串值字符補全

樸素的模式匹配算法

對主串的每一個字符作為子串開頭，與要匹配的字符進行匹配。對主串做大循環，每個字符開頭做T的長度的小循環，直到匹配成功或全部遍歷完成為止。

時間復雜度為O(n+m)

/* 返回子串T在主串S中第pos個字符之后的位置。若不存在,則函數返回值為0。 */
/* 其中,T非空,1≤pos≤StrLength(S)。 */
int Index(String S, String T, int pos) 
{
    int i = pos;    /* i用于主串S中當前位置下標值，若pos不為1，則從pos位置開始匹配 */
    int j = 1;                /* j用于子串T中當前位置下標值 */
    while (i <= S[0] && j <= T[0]) /* 若i小于S的長度并且j小于T的長度時，循環繼續 */
    {
        if (S[i] == T[j])     /* 兩字母相等則繼續 */
          {
            ++i;
             ++j; 
          } 
          else                 /* 指針后退重新開始匹配 */
          {  
             i = i-j+2;        /* i退回到上次匹配首位的下一位 */
             j = 1;             /* j退回到子串T的首位 */
          }      
    }
    if (j > T[0]) 
        return i-T[0];
    else 
        return 0;
}

利用上面的算法，假設我們要從主串goodgoogle中找到google，則需要下面的步驟

想想如果我們要在主串S="00000000000000000000000000000000000000000000000000001"，而要匹配的子串T=“0000000001”

也就是說T串需要在S串的前40個位置都需要判斷10次并得到不匹配的結論，直到第41位才全部匹配相等

因此最壞的情況的時間復雜度為O(((n-m)+1)*m)

KMP模式匹配算法原理

如果主串S="abcdefgab",要匹配的子串T="abcdex"

如果用樸素算法的話，則匹配的流程圖如下所示：

細想一下，子串T中“abcdex” 首字母a與后面的串“bcdex”中的任意一個字符都不相等，既然a不與自己后面的子串中任何一個字符相等，那么對于上圖1來說，前五個字符分別相等，意味著子串T的首字符a不可能與s串的第2位到第5位的字符相等，也就是說在上圖中2、3、4、5的判斷都是多余的。

如果子串T中有與首字符相等的字符，也是可以省略一部分不必要的判斷步驟的。

我們把T串各個位置的j值的變化定義為一個數組next，那么next的長度就是T串的長度

舉例說明next數組值推導

KMP模式匹配算法實現代碼

/* 通過計算返回子串T的next數組。 */
void get_next(String T, int *next) 
{
    int i,j;
      i=1;
      j=0;
      next[1]=0;
      while (i<T[0])  /* 此處T[0]表示串T的長度 */
     {
        if(j==0 || T[i]== T[j])     /* T[i]表示后綴的單個字符，T[j]表示前綴的單個字符 */
        {
              ++i;  
            ++j;  
            next[i] = j;
        } 
        else 
            j= next[j];    /* 若字符不相同，則j值回溯 */
      }
}

/* 返回子串T在主串S中第pos個字符之后的位置。若不存在，則函數返回值為0。 */
/*  T非空，1≤pos≤StrLength(S)。 */
int Index_KMP(String S, String T, int pos) 
{
    int i = pos;        /* i用于主串S中當前位置下標值，若pos不為1，則從pos位置開始匹配 */
    int j = 1;            /* j用于子串T中當前位置下標值 */
    int next[255];        /* 定義一next數組 */
    get_next(T, next);    /* 對串T作分析，得到next數組 */
    while (i <= S[0] && j <= T[0]) /* 若i小于S的長度并且j小于T的長度時，循環繼續 */
    {
        if (j==0 || S[i] == T[j])     /* 兩字母相等則繼續，與樸素算法增加了j=0判斷 */
          {
             ++i;
             ++j; 
          } 
          else             /* 指針后退重新開始匹配 */
               j = next[j];/* j退回合適的位置，i值不變 */
    }
    if (j > T[0]) 
        return i-T[0];
    else 
        return 0;
}

上面get_next的時間復雜度為O(m)，而index_KMP中while循環的時間復雜度為O(n)，所以整個算法的時間復雜度為O(n+m)

KMP模式匹配算法改進

比如主串S="aaaabcde"，子串T="aaaaax",那么next數組值分別為012345

利用KMP算法比較的過程如下圖所示：

當i=5,j=5時,b與a不相等，如上圖1

j=next[5]=4，如上圖2，b與第四個位置的a依然不等

j=next[4]=3，如上圖3,...

細想一下，2、3、4、5步驟都是多余的，因為T串的第二、三、四、五位置的字符都與首位a相等，那么可以利用首位的next[1]的值去取代與它相等的字符后續的next[j]的值

改良版的KMP算法實現代碼

/* 求模式串T的next函數修正值并存入數組nextval */
void get_nextval(String T, int *nextval) 
{
      int i,j;
      i=1;
      j=0;
      nextval[1]=0;
      while (i<T[0])  /* 此處T[0]表示串T的長度 */
     {
        if(j==0 || T[i]== T[j])     /* T[i]表示后綴的單個字符，T[j]表示前綴的單個字符 */
        {
              ++i;  
            ++j;  
            if (T[i]!=T[j])      /* 若當前字符與前綴字符不同 */
                nextval[i] = j;    /* 則當前的j為nextval在i位置的值 */
              else 
                nextval[i] = nextval[j];    /* 如果與前綴字符相同，則將前綴字符的 */
                                            /* nextval值賦值給nextval在i位置的值 */
        } 
        else 
            j= nextval[j];            /* 若字符不相同，則j值回溯 */
      }
}