简单的模式匹配算法

子串的定位操作通常称为串的模式匹配，它求的是子串（常称模式串）在主串中的位置。这里采用定长顺序存储结构，给出一种不依赖于其他串操作的暴力匹配算法。

  1. // 朴素模式匹配算法
  2. int Index2(SString S, SString T) {
  3.     int k = 1;  // 指向主串开始匹配的位置
  4.     int i = k;  // 主串匹配时的匹配位置 
  5.     int j = 1;  // 子串匹配时对应的位置
  6.     while (i <= S.length && j <= T.length) {
  7.         if (S.ch[i] == T.ch[j]) {  // 相等检查下一个字符
  8.             ++i;
  9.             ++j;
  10.         } else {  // 有不相等检查下一个子串
  11.             k++;
  12.             i = k; // 如果不设置k，i=i-j+2
  13.             j = 1;
  14.         }
  15.     }
  16.     // 如果因为主串匹配完导致结束需要判断子串是否刚好匹配
  17.     // 如果j超出边界说明子串得到匹配
  18.     if (j > T.length) {
  19.         return k;
  20.     } else {
  21.         return 0;
  22.     }
  23. }

在上述算法中，分别用计数指针 串的模式匹配 - 图1 和 串的模式匹配 - 图2 指示主串 串的模式匹配 - 图3 和模式串 串的模式匹配 - 图4 中当前正待比较的字符位置。算法思想为：从主串 串的模式匹配 - 图5 的第一个字符起，与模式 串的模式匹配 - 图6 的第一个字符比较，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起，重新和模式的字符比较；以此类推，直至模式 串的模式匹配 - 图7 中的每个字符依次和主串 串的模式匹配 - 图8 中的一个连续的字符序列相等，则称匹配成功，函数值为与模式 串的模式匹配 - 图9 中第一个字符相等的字符在主串 串的模式匹配 - 图10 中的序号，否则称匹配不成功，函数值为零。将主串中与模式串长度相同的子串搞出来，挨个与模式串对比当子串与模式串某个对应字符不匹配时，就立即放弃当前子串，转而检索下一个子串。

若 串的模式匹配 - 图11 为模式串长度，串的模式匹配 - 图12 为主串长度，则

  • 匹配成功的最好时间复杂度为：串的模式匹配 - 图13#card=math&code=O%28m%29&id=ldpN7)
  • 匹配失败的最好时间复杂度为：串的模式匹配 - 图14%3DO(n-m)%5Capprox%20O(n)#card=math&code=O%28n-m%2B1%29%3DO%28n-m%29%5Capprox%20O%28n%29&id=Dfc81)
  • 匹配成功的最坏时间复杂度为：串的模式匹配 - 图15%5Capprox%20O(nm)#card=math&code=O%28nm-m%5E2%2Bm%29%5Capprox%20O%28nm%29&id=Vpy9W)

最坏情况：每个子串的前 串的模式匹配 - 图16 个字符都和模式串匹配，只有第 串的模式匹配 - 图17 个字符不匹配；
比较好的情况：每个子串的第 1 个字符就与模式串不匹配。

KMP算法

由D. E.Knuth，J.H.Morris和 V.R.Pratt 提出，因此称为KMP算法

推荐直接看视频理解思想：数据结构，KPM算法

概况是对朴素模式匹配算法的优化，通过引入 next 数组来减少回溯。

  1. // KMP算法思想
  2. int Index_KMP(SString S, SString T, int next[]) {
  3.     int i = 1, j = 1;
  4.     while (i <= S.length && j <= T.length) {
  5.         if (j == 0 || S.ch[i] == T.ch[j]) {
  6.             ++i;
  7.             ++j;
  8.         } else {
  9.             j = next[j]; // 模式串向右移动
  10.         }
  11.     }
  12.     if (j > T.length) {
  13.         return i - T.length;
  14.     } else {
  15.         return 0;
  16.     }
  17. }

求模式串的next数组

  • 串的前缀：包含第一个字符，且不包含最后一个字符的子串。
  • 串的后缀：包含最后一个字符，且不包含第一个字符的子串.

next 数组手算方法：当第 j 个字符匹配失败，由前 1~j-1 个字符组成的串记为 S，则：next[j] = S 的最长相等前缀长度 +1，特别的 next[1] = 0；此外存在 next[2] 时 next[2] = 1。

KMP算法性能分析

  1. // 获取next数组
  2. void get_next(SString T, int next[]) {
  3.     int i = 1, j = 0;
  4.     next[1] = 0;
  5.     while (i < T.length) {
  6.         if (j == 0 || T.ch[i] == T.ch[j]) {
  7.             ++i;
  8.             ++j;
  9.             next[i] = j;
  10.         } else {
  11.             j = next[j];
  12.         }
  13.     }
  14. }
  16. // KMP算法实现
  17. int Index_KMP(SString S, SString T) {
  18.     int i = 1, j = 1;
  19.     int next[T.length + 1];
  20.     get_next(T, next);
  21.     while (i <= S.length && j <= T.length) {
  22.         if (j == 0 || S.ch[i] == T.ch[j]) {
  23.             ++i;
  24.             ++j;
  25.         } else {
  26.             j = next[j];
  27.         }
  28.     }
  29.     if (j > T.length) {
  30.         return i - T.length;
  31.     } else {
  32.         return 0;
  33.     }
  34. }

KMP 算法平均时间复杂度：串的模式匹配 - 图18#card=math&code=O%28n%2Bm%29&id=KpUy4)

KMP算法优化

next 数组在某些情况下尚有缺陷，还可以进一步优化。

// nextval
void get_nextval(SString T, int nextval[]) {
    int i = 1, j = 0;
    nextval[1] = 0;
    while (i < T.length) {
        if (j == 0 || T.ch[i] == T.ch[j]) {
            nextval[i] = j;
            if (T.ch[i] != T.ch[j]) {
                nextval[i] = j;
            } else {
                nextval[i] = nextval[j];
            }
        } else {
            j = nextval[j];
        }
    }
}