用字符“画”字符串的相关匹配算法。
说明
以S代表字符串，下面是相关术语说明。
相等：
S[0,n) = T[0,m)
长度相等，且对应的字符相同
子串：
substr(i,k) = S[i, i+k), 0<= i < n, 0 <= k
从S[i]起的连续k个字符
前缀：
prefix(k) = substr(0,k) = S[0,k), 0 <= k <= n
最靠前k个字符
后缀：
suffix(k) = substr(n-k, k) = S[n-k, n), 0 <= k <= n
最靠后的k个字符
空串：
S[0, n=0)
蛮力匹配
蛮力匹配即是依次比较两个字符串的每一个字符，效率低下。
- 方式1：
时间复杂度：
len(P) = m , len(T) = n
O(n+m) <= BF <= O(n*m)
示意图：
P: Pattern，模式字符，即待匹配的字符
T: Text，文本字符
i
Text: ------ [ ] X -------------
Pattern: [ ] Y [ ]
j
每次匹配失败：T回退 j 个字符，重新从P[0]开始比较
若匹配成功 ：则i-j为P在T首次出现位置（第一个字符）的下标
- 方式2：
时间复杂度：
len(P) = m , len(T) = n
O(n+m) <= BF <= O(n*m)
示意图：
P: Pattern，模式字符，即待匹配的字符
T: Text，文本字符
i i+j
Text: ------ [ ] X -------------
Pattern: [ ] Y [ ]
j
每次匹配失败：重新从P[0]开始比较
若匹配成功 ：则i为P在T首次出现位置（第一个字符）的下标
KMP匹配
KMP利用P中匹配成功的前缀信息，来确定新的匹配起始点；
匹配概率越高，优势越明显。
适合小字符集的匹配（如数字字符集，英文字母字符集）；
KMP算法
(1)KMP的基本思想如下：
失配点
/
Text : c h i n c h i *
0 1 2 3 4 5 6 7 8 9 -> 字符的下标j
Pattern : c h i n c h i l l a
-1 0 0 0 0 1 2 3 0 0 -> next[j]
next[j] : c h i n c h i l l a
在 P[j=7]=l 匹配失败时，不必从P[j=0]重新开始匹配，而是从 next[j=7]=P[j=3]=n 开始匹配；
因为 P[j=4,5,6]=chi 和 P[j=0,1,2] 相同的，不需要再次匹配（因此KMP算法需要先建立next表）；
(2)时间复杂度：
len(P) = m , len(T) = n
KMP = O(n+m)
建立next表
Next[j]的建立：
i -> 失配点下标
Text: ---------- { }{ P[j-t,j) } x ----------
j -> 失配点下标
Pattern: { P[0,t) }{ } y -----
t -> 新的比较点
j-t { P[0,t) } z -------
当P[j-t,j) 与 P[0,t)相等，则无需要再比较，直接从新的比较点t开始匹配
对任意失配点j，next[j]的值为：
next[j] = N(P,j) = { 0 <= t < j | P[0,t) == P[j-t, j) }
即：
在P的前缀P[0,j)中，P[0,j)的真前缀P[0,t)和真后缀P[j-t,j)匹配的长度，就是next[j]；
若有多个匹配的真前缀和真后缀，则取长度最长的（即使得移动距离j-t最小）；
因为“大”长度的，肯定包含了“小”长度真前缀和真后缀。
可推出：
next[j+1] <= next[j] + 1
当且仅当 P[j] == P[next[j]] 时取等号
理解如下：
j+1
[ P[0,j+1) | ]
j|
[ P[0,j) || ]
[ *******#? ] => P[j] = #, next[j] = 7, next[j] < j （真后缀的长度比P[0,j)的长度小）
[*******#? ] => P[7] = # = P[next[j]]，则有P[j] = P[next[j]]
--------
此段是 P[0,j) 的真前缀和真后缀，其长度，也即 * 的个数，就是next[j] = 7 (注意P[0,j)未包括j)；
而next[j+1]相对于next[j]多了个 #，即P[0,j+1)的真前缀和真后缀匹配的长度加1
改进版next表
设P与T进行匹配，且匹配到了T[i]处
(1)情况一：接连好几个字符相同
j j+1
[0 0 0 0 0 0 1]
-1 -1 -> next[j]
t t+1
若P[j] = P[t] 且 P[j+1] = P[t+1]，则next[j+1] = next[t+1] = -1；
同理一直推下去，可知前6个0的next均为-1；
这样，若T[i]与P[j+1]失配，可以让P直接从头开始比较，
P[j+1]左侧的相同的0无需再比较（比较也肯定失配）。
(2)情况二：普通情况
j j+1
[a b c * a b #]
-1 0 0 0 1 -> next[]
-1 0 0 -1 0 -> next_improved[]
t t+1
若P[j] = P[t] 且 P[j+1] = P[t+1]，则next[j+1] = next[t+1] = 0；
按原来算法，若T[i]与P[j+1]失配，
接着，应该让T[i]与 P[next[j+1]] = P[t+1] 比较
按照改进算法，若T[i]与P[j+1]失配，
接着，直接让T[i]与 P[next[j+1] = P[0] 比较，
因为既然T[i] != P[j+1]，也就有T[i] != P[t+1]，再比较T[i]与P[t+1]肯定也是失配
可以这样来理解：j+1指向处于P中的自相似的子串"ab"，第一个子串失配了，另一个子串也必然失配。
BM匹配
BM算法利用P匹配失败的信息，来确定新的匹配起始点；
首次失配的概率越大，性能优势越明显；
适合大字符表（如中文字符集）。
BM算法
时间复杂度：
len(P) = m , len(T) = n
O(n/m) <= BC <= O(n*m)
O(n/m) <= BC+GS <= O(n+m)
从右向左，对字符串进行比对。
i i+j
Text: ------ [ ] X [*****]----------
Pattern: [ ] Y [*****]
j: 失配点
bc表：
失配之处为“教训”，要想匹配成功，下一次比对的Pattern字符应当为Text中失配字符。
gs表：
失配之处为“经验”，与KMP类似，借助模式字符串的自相似性。
建立bc表
bc表：bad-character
i i+j
Text: ------ [ ] X [*****]----------
| |
| | j: 失配点
Pattern: [ ] Y [*****]
| |
| [ ] X [ ]
t = bc['X']
P在P[j]处失配，若要在T[i+j]处成功匹配，则P中应该也有一个字符X；
故可以直接右移 j-bc['X'] 重新进行比较（bc['X']表示字符X在P中的下标）。
特殊情况1：P中有多个字符X时，取下标最大的字符X（即P中在t右侧的子串，不能再有字符X）
特殊情况2：P中没有字符X时，取bc['X']=-1（类似的，-1为假想的通配符位置，同时，P中在t右侧的子串中，必定没有字符X）
特殊情况3：bc['X'] > j 时（即X在Y的右侧），则只需向右移1个字符，不需要向左移；
因为在 i 左侧的位置，都已经排除了，不可能发生成功的匹配；
且若有多个字符X时，在j左侧也可能有X（但下标不是最大的），故只能向右移一个字符。
总结：
情况1,2：右移j-bc['X']， 则i = i+j-bc['X']，情况2即为i = i+j+1
情况3： 右移1
建立gs表
gs表：good suffix
在不确定P中失配点j左侧有没有字符X时，才用gs表（即bc表的情况三）
i i+j
Text: ------ [ ] X [abcde]----------
| |
| | j: 失配点
Pattern: [ ] Y [abcde]
| | \
| | good suffix为P的子串(若有多个good suffix，取使gs[j]最小的，即k最大的)
| | k /
Pattern: | [ ] # [abcde ]
gs[j] = j-k && P[gs[j]]！= 'Y'
h (good suffix为P的前缀)
Pattern: [cde ]
gs[j] = len(P) - h
P在P[j]处失配，则i直接向右移gs[j]距离。
(1) gs为子串和前缀时的区别：
Text: -----------------X--------------
|<-- r1 -->| => 子串与后缀匹配
i | j |
Pattern: [abc # abc X * X abc]
| k |
|<------- r2 ------->| => 前缀与后缀匹配
在 P[j] = * 处失配时，向右移r1；当然，会不会漏掉 P[k] = X 的对齐位置呢？不会，因为若要在 P[k] 处成功匹配
所有字符串，则 P[k] 与 P[j] 之间必定含有子串 abc，那么 r1 距离的起点就应
该在 P[k] 与 P[j] 之间
在 P[i] = # 处失配时，向右移r2；
(2) 由ss计算gs：
j，ss[j] = 4
[abcd abcd]
ss[j]：即在P中与P后缀相同，且以P[j]为未字符的子串(或前缀)的长度
(2.1)若存在为前缀的good suffix，必有 ss[j]=j+1, ss[i]=i+1：
0 i j k h
[abcabc abcabc]
[abcabc abcabc]
[abcabc abcabc]
在[0,k)之间发生失配时，均可以右移gs[x] = Len(P)-ss[j] = Len(P)-(j+1)
在[k,h)之间发生失配时，均可以右移gs[x] = Len(P)-ss[i] = Len(P)-(i+1)
其中有：k = Len(P) - (j+1)
h = Len(P) - (i+1)
(2.2)若存在为子中的good suffix，必有ss[j] < j+1：
0 j i: 失配点
[ abc abc]
[abcd abcd]
在i失配，则右移gs[i] = Len(P) - (j+1), i = Len(P) - ss[j] - 1
ss[j] = 0 : i = Len(P) - ss[j] - 1 = max-index
0 < ss[j] < j+1 : i = Len(P) - ss[j] - 1
(3) 示例：
0 1 2 3 4 5 6 7 => index
非 曰 静 也 善 故 静 也
A B C D E F C D
0 0 0 2 0 0 0 8 => ss
8 8 8 8 8 4 8 1 => gs
A B A B x y z A B A B
0 2 0 4 0 0 0 0 2 0 11 => ss
7 7 7 7 7 7 7 9 2 11 1 => gs
代码参考
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 [ yehuohan@gmail.com ]