数据结构——串（朴素的模式匹配算法、KMP模式匹配算法）

键盘上的钢琴师_v5

提示：以下内容不适合零基础人员，仅供笔者复习之用。

概要：

串是由零个或多个字符组成的有限序列，又名叫字符串。

一、串的比较

    给定两个串，s = "a1a2.....an"，t="b1b2....bm"，当满足以下条件之一时，s<t。

1. n<m，且ai = bi（i=1,2,.....,n）。例如，s="hap"，t="happy"，就有s<t。
2. 存在某个k<=min(m,n)，使得ai = bi（i=1,2,.....,k-1）,ak < bk。例如，s="happen"，t="happy"，因为两串前4个字母均相同，而两串第5个字母（k值）, e 的ASCII码是101，而 y 的ASCII码是121，显然 e < y，所以s<t。

二、串的抽象数据类型

    串的逻辑结构与线性表相似，不同之处在于串针对的是字符集，每个元素都是字符。此外，串的基本操作与线性表有很大差别。线性表关注的是单个元素的操作，串中更多则是查找子串位置、得到指定位置子串、替换子串等操作。

 

三、串的存储结构

1. 串的顺序存储结构

    用一组地址连续的存储单元来存储串中的字符序列。一般用定长数组为每个定义的串变量分配一个固定长度的存储区。这样的存储方式存在问题，因为定长，在字符串操作时候，比如连接、插入新串、替换等操作时，都可能使串序列的长度超过了数组的长度MaxSize。

 

2. 串的链式存储结构

    与线性表相似，但因为串中每个元素都是一个字符，如果用链表存储串值，一个结点对应一个字符，就会存在很大的空间浪费。因此，一个结点可以存放一个字符，可以考虑存放多个字符，最后一个结点若是未被占满，可用“#”或其他非串值字符补全，如图。

    当然，一个结点存多少个字符才合适显得很重要，这会影响串处理的效率，要根据实际情况取舍。总的来说，串的链式存储结构除了在连接串与串操作时有一定方便之外，不如顺序存储灵活，性能也不如顺序存储结构好。

 

四、朴素的模式匹配算法

    串的模式匹配：子串的定位操作。

1.  算法思想

    假设从主串S = “goodgoogle”中找T = “google”这个子串的位置。要按以下步骤：（竖线表示相同，折线表示不同）

    

 

    

 

        ……

 

    

    简单地说，就是对主串的每一个字符作为子串开头，与要匹配的字符串进行匹配。此过程中，对主串做大循环，每个字符开头做T的长度的小循环，直到匹配成功或全部遍历完成为止。假设主串S和匹配的子串T的长度存在S[0]与T[0]中，该算法实现如下：

1. /* 返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数返回值为0。 */

2. /* 其中,T非空,1≤pos≤StrLength(S)。 */

3. int Index(String S, String T, int pos)

4. {

5. int i = pos; /* i用于主串S中当前位置下标值，若pos不为1，则从pos位置开始匹配 */

6. int j = 1; /* j用于子串T中当前位置下标值 */

7. while (i <= S[0] && j <= T[0]) /* 若i小于S的长度并且j小于T的长度时，循环继续 */

8. {

9. if (S[i] == T[j]) /* 两字母相等则继续 */

10. {

11. ++i;

12. ++j;

13. }

14. else /* 指针后退重新开始匹配 */

15. {

16. i = i-j+2; /* i退回到上次匹配首位的下一位 */

17. j = 1; /* j退回到子串T的首位 */

18. }

19. }

20. if (j > T[0])

21. return i-T[0];

22. else

23. return 0;

24. }

    该算法中最关键的步骤是回退过程：

        两字母相等时，在小循环内继续循环比较。

        两字母不等时，则回退。对于i，回退的位置是i = i - j +2。对于j，回退到1，重新从开始比较待匹配串。有读者可能不理解i的回退位置如何计算的，且看以下图示，假设pos = 3。

    图中，①开始进入while循环，因为n ≠ d，进入else回退。此时应该从i的下一位 d 再开始比较，i - j 回退到o位置，再加 2 则恰好进到 d 位置；j = 1，即j位置不变。如图②。

    ②中因为d = d，进入小循环，i、j不断累加（while ->if -> while -> if -> while ...），直到图③，f ≠ r，再回退，此时应该从开始进入小循环的i的下一位 e 再开始比较，i - j 回退到n位置，再加 2 则恰好进到 e 位置；j = 1，即j回到最初位置。如图④。以同样方式，再继续循环比较，不再赘述。

    综上，i - j +2就是主串长度减去已匹配的子串长度，再加2，则进位到下一个要匹配的主串位置。（加1就是进入小循环的位置）

 

2.  时间复杂度

    朴素模式匹配算法时间复杂度分析如下：（n为主串长度，m为模式串长度）

情况	时间复杂度	备注
最好情况	O(1)	一开始就匹配成功。
最坏情况	O((n-m+1)*m)	每次不成功的匹配都发生在模式串的最后一个字符。
平均情况	O(n+m)	根据等概率原则，平均是(n+m)/2次查找。

   

    最好情况，只用在第一个字符所在的大循环中比较m次，m为较小的常数，可当做时间复杂度为O（1）。如在“googleasdfhjklqweruiopqwer”中找“google”。（个人理解，如有误，恳请读者留言指正）

    最坏情况，就是每次不成功的匹配都发生在串T的最后一个字符。如：主串为S = “000000000000000000000000000000000000000000000000001”，而要匹配的子串为T = “0000000001”，前者是49个“0”和1个“1”的主串，后者是9个“0”和1个“1”的子串。每次匹配都将T中字符循环到最后一位才发现不匹配，这样等于T串要在S串的前40个位置的每个位置都要判断10次，并得出不匹配的结论，直到最后第41个位置，因为全部匹配相等，所以不需要再继续进行下去，如下图。如果最终没有可匹配的子串，比如是T =“0000000002”,到了第41位置判断不匹配后同样不需要继续比对下去。因此最坏情况比较次数为(n-m+1)*m。如图所示。

    一般（平均）情况，若第一次就匹配成功，对比了m次，若把主串遍历完也没有和子串匹配上，则对比了n次。所以，平均对比了(n+m)/2次。（个人理解，如有误，恳请读者留言指正）

    以上特别是最坏情况下，效率极低。由此引入改进的模式匹配算法——KMP模式匹配算法。

 

五、KMP模式匹配算法

1. 算法关键

       如果主串S= “abcdefgab”，子串T= “abcdex”，用上面的朴素算法的话，前5个字母，两串完全相等，直到第6个字母，“f”与“x”不等，如下图。接下来进行②③④⑤⑥的步骤，而T中“a”与后边的每一位都不同，对于①中，前5位已经相同，所以，T中“a”也不会与S中的第2-5位相同，则②③④⑤的判断是多余的。只用保留①⑥，之所以保留⑥，是因为在①中T[6]≠S[6]，尽管我们已经知道T[1]≠T[6]，但也不能断定T[1]一定不等于S[6]，因此需要保留⑥。

      假设主串S= “abcabcabc”，子串T= “abcabx”，前5个相对，第6个不等。根据刚刚的经验，T的首字符“a”与第二位“b”、第三位“c”均不相等，所以不需要做判断，下图中②③是多余的。又因为T的首位与第四位相等，T的第二位与第五位相等，而在①中，子串中第四位的“a”与第五位的“b”已经与主串S中相应的位置比较过了，是相等的，因此可以断定，T的首字符“a”、第二位的“b”与S的第四、第五位字符也不需要比较了，肯定也是相等的——之前比较过了，不需要再次判断，所以④⑤这两个步骤也可以省略。（即T前部=T后部，T后部=S后部，则T前部=S后部）

,

      对比发现，i的值从6-2-3-4-5-6，即在朴素的模式匹配算法中，主串的i值是不断地回溯来完成的，而我们分析发现，这种回溯过程是可以不需要的。KMP算法就是为了让没必要的回溯不发生。既然i不回溯（不会变小），我们就要考虑j值的变化了。对比上面两图，我们发现，j的变化与T串的首字符和自身后面字符是否相等有关，而与主串无关，即j值的变化关键取决于T串的结构中是否有重复的问题。如一图中，T=“abcdex”，当中没有任何重复字符，所以j由6变为1，二图中，T=“abcabx”，前缀“ab”与最后“x”前的“ab”相等，因此j就由6变成了3。因此可以得出规律，j值的多少取决于当前字符之间的串的前后缀的相似度。我们把T串各位置的j值的变化定义为一个数组next，那么next的长度就是T串的长度，则有如下函数定义：

 

2. next数组值推导

    看两个例子。（取自书中）

    我们可以根据经验得到：如果前后缀一个字符相等，k值是2，两个字符相等k值是3，n个字符相等k值就是n+1。

 

3. KMP模式匹配算法实现

1. /* 通过计算返回子串T的next数组。 */

2. void get_next(String T, int *next)

3. {

4. int i,j;

5. i=1;

6. j=0;

7. next[1]=0;

8. while (i<T[0]) /* 此处T[0]表示串T的长度 */

9. {

10. if(j==0 || T[i]== T[j]) /* T[i]表示后缀的单个字符，T[j]表示前缀的单个字符 */

11. {

12. ++i;

13. ++j;

14. next[i] = j;

15. }

16. else

17. j= next[j]; /* 若字符不相同，则j值回溯 */

18. }

19. }

    这段代码的目的就是为了计算出当前要匹配的串T的next数组。

1. /* 返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0。 */

2. /* T非空，1≤pos≤StrLength(S)。 */

3. int Index_KMP(String S, String T, int pos)

4. {

5. int i = pos; /* i用于主串S中当前位置下标值，若pos不为1，则从pos位置开始匹配 */

6. int j = 1; /* j用于子串T中当前位置下标值 */

7. int next[255]; /* 定义一next数组 */

8. get_next(T, next); /* 对串T作分析，得到next数组 */

9. while (i <= S[0] && j <= T[0]) /* 若i小于S的长度并且j小于T的长度时，循环继续 */

10. {

11. if (j==0 || S[i] == T[j]) /* 两字母相等则继续，与朴素算法增加了j=0判断 */

12. {

13. ++i;

14. ++j;

15. }

16. else /* 指针后退重新开始匹配 */

17. j = next[j];/* j退回合适的位置，i值不变 */

18. }

19. if (j > T[0])

20. return i-T[0];

21. else

22. return 0;

23. }

 

4. KMP的时间复杂度

    3中相对于朴素匹配算法增加的代码，主要去掉了i的回溯部分。首先分析KMP的核心算法流程，假设现在文本串S匹配到 i 位置，模式串T匹配到 j 位置：

• 如果当前字符匹配成功（即S[i] == T[j]），则令++i，++j，继续匹配下一个字符；
• 如果当前字符匹配失败（即S[i] != T[j]），则令 i 不变，j = next[j]。意味着匹配失配时，模式串T相对于文本串S向右移动了j - next [j] 位。

    正如前文，若主串S= “abcabcabc”，子串T= “abcabx”，由T得next[j] = [0,1,1,1,2,3]，因为S[6]（这里下标i、j从1开始）≠T[6]，所以，j=next[6]=3，T相当于移动了6-3=3个位置。如图：

》》》》》

    对于get_next函数而言，若T的长度为m，因只涉及简单的单循环，其时间复杂度为O（m），而由于i不回溯，使得index_KMP算法效率得到了提高，while循环的时间复杂度为O（n），以上两个函数先后线性执行，因此，整个算法的时间复杂度为O（n+m）。相较于朴素模式匹配算法的O（（n-m+1）*m）来说，是要好一些。需要说明的是，KMP算法仅当模式与主串之间存在许多“部分匹配”的情况下才体现出它的优势，否则和朴素模式匹配算法相比，差异并不明显。

 

5. KMP模式匹配算法改进

    后来有人发现，KMP还是有缺陷的。比如，如果我们的主串S = “aaaabcde”，子串T = “aaaaax”，其next数组值分别为012345，在开始时，当i=5、j=5时，我们发现“b”与“a”不相等，如下图①，因此j=next[5]=4，如图②，此时“b”与第4位置的“a”依然不等，j=next[4]=3，如图③，后依次是④⑤，直到j=next[1]=0时，根据算法，此时i++、j++，得到i=6、j=1，如图⑥。

    我们发现，当中的②③④⑤其实是多余的，由于T的第二、三、四、五位的字符与首位“a”相等，那么可以用首位next[1]的值去取代与它相等的字符后续next[]的值，这是个很好的办法，对next数组进行优化。假设取代的数组为nextval，增加了部分，如下：

 

1. /* 求模式串T的next函数修正值并存入数组nextval */

2. void get_nextval(String T, int *nextval)

3. {

4.       int i,j;

5.       i=1;

6.       j=0;

7.       nextval[1]=0;

8.       while (i<T[0])  /* 此处T[0]表示串T的长度 */

9.      {

10.         if(j==0 || T[i]== T[j])     /* T[i]表示后缀的单个字符，T[j]表示前缀的单个字符 */

11.         {

12.               ++i;  

13.             ++j;  

14.             if (T[i]!=T[j])      /* 若当前字符与前缀字符不同 */

15.                 nextval[i] = j;    /* 则当前的j为nextval在i位置的值 */

16.               else

17.                 nextval[i] = nextval[j];    /* 如果与前缀字符相同，则将前缀字符的 */

18.                                             /* nextval值赋值给nextval在i位置的值 */

19.         }

20.         else

21.             j= nextval[j];            /* 若字符不相同，则j值回溯 */

22.       }

23. }

 

 

6. nextval数组值推导

    改良后，nextval值就与next值不完全相同了，如下例子：

    总结改进过的KMP算法，它是在计算出next值的同时，如果a位字符与它next值指向的b位字符相等，则该a位的nextval 就指向b位的nextval值，如果不等，则该a位的nextval值就是它自己a位的next的值。

 

 

参考：

《大话数据结构》