在代碼中的模式匹配往往都是寫好的接口, 基本上只需要用一句代碼可以實現(xiàn).

匹配字符串中的子字符是如何實現(xiàn)的呢? 假設(shè)我們以 S 代表目標(biāo)串,即父串(例如 aeaaefababdc), 以 T 代表模式串即子串(例如 abd), i 代表 S 中字符位置, j 代表 T 中字符位置, 即下標(biāo). 我們要做的是匹配是否 abcdefabdc 中存在 aeaad.

• 最常用的是使用樸素匹配算法
  樸素匹配算法的原理是使用模式串 T 和目標(biāo)串 S 的每一個字符都進(jìn)行比較, 是一種有回溯的算法. 算法的時間復(fù)雜度無 O(m+n), m,n 分別代表目標(biāo)串和模式串的長度.
  1 首先我們令 i = 0, j = 0.
  2 把 S 的第一個字符 S[0] 和 T 的第一個字符 T[0] 進(jìn)行比較. (例子中 S[0] = T[0] = a)
  3 如果相同則 i, j 分別+1 . (例子中 繼續(xù)比較 S[1] 和 T[1], S[1] = T[1] = b)
  4 直到出現(xiàn)不相同S[i] != T[j]. (例子中 S[4] = e != T[4] = d)
  5 重新比較 S 的第二個字符 S[1] 和 T 的第一個字符 T[0] , 重復(fù)執(zhí)行步驟3,4直到匹配成功或所有都匹配不成功.
• KMP 匹配算法
  在許多時候, 樸素算法的回溯增加了大量的運(yùn)算時間, 特別是當(dāng)模式串和主串有許多部分匹配的情況下. 因此 D. E. Kunth 與 J. H. Morris 和 V. R. Pratt對算法做出了改進(jìn), 使得算法不需要回溯, 并且可以在 O(m+n)的時間復(fù)雜度上完成串的匹配, 稱為 KMP 匹配算法.
  KMP 匹配算法相對樸素匹配算法的改進(jìn)之處在于, KMP 匹配算法會對匹配串本身進(jìn)行一次匹配, 目的是為了當(dāng)匹配串和目標(biāo)串"失配"時, 確定模式串中和需重新和主串中的"失配"那一位字符進(jìn)行比較的位置. 即模式串的 next[j] 函數(shù).
  1 首先我們令 i = 0, j = 0.
  2 把 S 的第一個字符 S[0] 和 T 的第一個字符 T[0] 進(jìn)行比較. (例子中 S[0] = T[0] = a)
  3 如果相同則 i, j 分別+1, 繼續(xù)比較 S[1] 和 T[1]. (例子中 S[1] = T[1] = b)
  4 直到出現(xiàn)不相同S[i] != T[j]. (例子中 S[2] = c != T[2] = d)
  5 模式串 T 退回到 next[j] 指示位置與 S 失配位置 S[i] 進(jìn)行比較. (例子中next[j] = 2, 對比S[4] = e 和 T[2] = a, 從而跳過了 S[1] - S[3] 以及 T[0] 和 T[1] 的比較.)
  6 重復(fù)3,4,5直到匹配成功或所有都匹配不成功.
• 雖然 KMP 匹配算法無需回溯, 但是僅有當(dāng)模式串和主串有許多部分匹配的情況下在時間復(fù)雜度上有明顯的優(yōu)勢. 又因為樸素匹配模式算法在一般情況下執(zhí)行時間近似 O(m+n), 因此樸素匹配模式算法仍在被大量采用.