前言
本篇章主要介紹串的KMP模式匹配算法及其改進，并用Python實現(xiàn)KMP算法。
1. BF算法
BF算法，即
undefined
Bruce−Force算法，又稱暴力匹配算法。其思想就是將主串S的第一個字符與模式串T的第一個字符進行匹配，若相等，則繼續(xù)比較S的第二個字符和T的第二個字符;若不相等，則比較S的第二個字符和T的第一個字符，依次比較下去，直到得出最后的匹配結(jié)果。
假設(shè)主串
undefined
S=ABACABAB，模式串
undefined
T=ABAB，每趟匹配失敗后，主串S指針回溯，模式串指針回到頭部，然后再次匹配，過程如下：
def BF(substrS, substrT):
if len(substrT) > len(substrS):
return -1
j = 0
t = 0
while j < len(substrS) and t < len(substrT):
if substrT[t] == substrS[j]:
j += 1
t += 1
else:
j = j - t + 1
t = 0
if t == len(substrT):
return j - t
else:
return -1
2. KMP算法
KMP算法，是由
undefined
D.E.Knuth、J.H.Morris、V.R.Pratt同時發(fā)現(xiàn)的，又被稱為克努特-莫里斯-普拉特算法。該算法的基本思路就是在匹配失敗后，無需回到主串和模式串最近一次開始比較的位置，而是在不改變主串已經(jīng)匹配到的位置的前提下，根據(jù)已經(jīng)匹配的部分字符，從模式串的某一位置開始繼續(xù)進行串的模式匹配。
就是這次匹配失敗時，下次匹配時模式串應(yīng)該從哪一位開始比較。
BF算法思路簡單，便于理解，但是在執(zhí)行時效率太低。在上述的匹配過程中，第一次匹配時已經(jīng)匹配的
undefined
"ABA"，其前綴與后綴都是
undefined
"A"，這個時候我們就不需要執(zhí)行第二次匹配了，因為第一次就已經(jīng)匹配過了，所以可以跳過第二次匹配，直接進行第三次匹配，即前綴位置移到后綴位置，主串指針無需回溯，并繼續(xù)從該位開始比較。
前綴：是指除最后一個字符外，字符串的所有頭部子串。
后綴：是指除第一個字符外，字符串的所有尾部子串。
部分匹配值
undefined
(Partial
undefined
Match,PM)：字符串的前綴和后綴的最長相等前后綴長度。
例如，
undefined
′a′的前綴和后綴都為空集，則最長公共前后綴長度為0;
undefined
′ab′的前綴為
undefined
{a}，后綴為
undefined
{b}，則最長公共前后綴為空集，其長度長度為0;
undefined
′aba′的前綴為
undefined
{a,ab}，后綴為
undefined
{a,ba}，則最長公共前后綴為
undefined
{a}，其長度長度為1;
undefined
′abab′的前綴為
undefined
{a,ab,aba}，后綴為
undefined
{b,ab,bab}，則最長公共前后綴為
undefined
{ab}，其長度長度為2。
前綴一定包含第一個字符，后綴一定包含最后一個字符。
1
如果模式串號位與主串當(dāng)前位(箭頭所指的位置)不匹配，將模式串1號位與主串的下一位進行比較。next[0]=-1，這邊就是一個特殊位置了，即如果主串與模式串的第1位不相同，那么下次就直接比較各第2位的字符。
2
如果模式串號位與主串當(dāng)前位不匹配，找最長公共前后綴，指針前面的子串為
undefined
1
"A"，即最長公共前后綴為空集，其長度為0，則下次匹配時將模式串號位與主串的當(dāng)前位進行比較。next[1]=0
3
如果模式串號位與主串當(dāng)前位不匹配，找最長公共前后綴，指針前面的子串為
undefined
1
"AB"，即最長公共前后綴為空集，其長度為0，則下次匹配時將模式串號位與主串的當(dāng)前位進行比較。next[2]=0
4
如果模式串號位與主串當(dāng)前位不匹配，找最長公共前后綴，指針前面的子串為
undefined
"ABA"，即最長公共前后綴為
undefined
2
"A"，其長度為1，則下次匹配時將前綴位置移到后綴位置，即模式串號位與主串的當(dāng)前位進行比較。next[3]=1
5
如果模式串號位與主串當(dāng)前位不匹配，找最長公共前后綴，指針前面的子串為
undefined
"ABAA"，即最長公共前后綴為
undefined
2
"A"，其長度為1，則下次匹配時將前綴位置移到后綴位置，即模式串號位與主串的當(dāng)前位進行比較。next[4]=1
6
如果模式串號位與主串當(dāng)前位不匹配，找最長公共前后綴，指針前面的子串為
undefined
"ABAAB"，即最長公共前后綴為
undefined
3
"AB"，其長度為2，則下次匹配時將前綴位置移到后綴位置，即模式串號位與主串的當(dāng)前位進行比較。next[5]=2
7
如果模式串號位與主串當(dāng)前位不匹配，找最長公共前后綴，指針前面的子串為
undefined
1
"ABAABC"，即最長公共前后綴為空集，其長度為0，則下次匹配時將模式串號位與主串的當(dāng)前位進行比較。next[6]=0
8
如果模式串號位與主串當(dāng)前位不匹配，找最長公共前后綴，指針前面的子串為
undefined
"ABAABCA"，即最長公共前后綴為
undefined
2
"A"，其長度為1，則下次匹配時將模式串號位與主串的當(dāng)前位進行比較。next[7]=1
綜上，可以得到模式串的next數(shù)組，發(fā)現(xiàn)沒有，把主串去掉也可以得到這個數(shù)組，即下次匹配時模式串向后移動的位數(shù)與主串無關(guān)，僅與模式串本身有關(guān)。
| 位編號 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 索引 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 模式串 | A | B | A | A | B | C | A | C |
| next | -1 | 0 | 0 | 1 | 1 | 2 | 0 | 1 |
next數(shù)組，即存放的是每個字符匹配失敗時，對應(yīng)的下一次匹配時模式串開始匹配的位置。
如何在代碼里實現(xiàn)上述流程呢?舉個栗子，藍色方框圈出的就是公共前后綴，假設(shè)next[j]=t：
當(dāng)
undefined
Tj?=Tt?時，可以得到
undefined
next[j+1]=t+1=next[j]+1。這個時候
undefined
j=4,t=1(索引);
當(dāng)
undefined
Tj??=Tt?時，即模式串
undefined
t位置與主串(并不是真正的主串)不匹配，則將下面的那個模式串移動到
undefined
next[t]位置進行比較，即
undefined
t=next[t]，直到
undefined
Tj?=Tt?或
undefined
t=−1，當(dāng)
undefined
t=−1時，
undefined
next[j+1]=0。這里就是
undefined
t=next[2]=0，即下次匹配時，模式串的第1位與主串當(dāng)前位進行比較。
代碼如下：
def getNext(substrT):
next_list = [-1 for i in range(len(substrT))]
j = 0
t = -1
while j < len(substrT) - 1:
if t == -1 or substrT[j] == substrT[t]:
j += 1
t += 1
# Tj=Tt, 則可以到的next[j+1]=t+1
next_list[j] = t
else:
# Tj!=Tt, 模式串T索引為t的字符與當(dāng)前位進行匹配
t = next_list[t]
return next_list
def KMP(substrS, substrT, next_list):
count = 0
j = 0
t = 0
while j < len(substrS) and t < len(substrT):
if substrS[j] == substrT[t] or t == -1:
# t == -1目的就是第一位匹配失敗時
# 主串位置加1, 匹配串回到第一個位置(索引為0)
# 匹配成功, 主串和模式串指針都后移一位
j += 1
t += 1
else:
# 匹配失敗, 模式串索引為t的字符與當(dāng)前位進行比較
count += 1
t = next_list[t]
if t == len(substrT):
# 這里返回的是索引
return j - t, count+1
else:
return -1, count+1
3. KMP算法優(yōu)化版
上面定義的next數(shù)組在某些情況下還有些缺陷，發(fā)現(xiàn)沒有，在第一個圖中，我們還可以跳過第3次匹配，直接進行第4次匹配。為了更好地說明問題，我們以下面這種情況為例，來優(yōu)化一下KMP算法。假設(shè)主串
undefined
S=AAABAAAAB，模式串
undefined
T=AAAAB，按照KMP算法，匹配過程如下：
可以看到第2、3、4次的匹配是多余的，因為我們在第一次匹配時，主串
undefined
4
S的號位為模式串
undefined
4
T的號位就已經(jīng)比較了，且
undefined
T3??=S3?，又因為模式串
undefined
T的4號位與其1、2、3號位的字符一樣，即
undefined
T3?=T2?=T1?=T0??=S3?，所以可以直接進入第5次匹配。
那么，問題出在哪里???我們結(jié)合著next數(shù)組看一下：
| 位編號 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 索引 | 0 | 1 | 2 | 3 | 4 |
| 模式串 | A | A | A | A | B |
| next | -1 | 0 | 1 | 2 | 3 |
問題在于，當(dāng)
undefined
Tj??=Sj?時，下次匹配的必然是
undefined
Tnext[j]?與
undefined
Sj?，如果這時
undefined
Tnext[j]?=Tj?，那么又相當(dāng)于
undefined
Tj?與
undefined
Sj?進行比較，因為它們的字符一樣，毫無疑問，這次匹配是沒有意義的，應(yīng)當(dāng)將
undefined
next[j]的值直接賦值為-1，即遇到這種情況，主串與模式串都從下一位開始比較。
所以，我們要修正一下next數(shù)組。
大致流程和上面求解next數(shù)組時一樣，這里就是多了一個判別條件，如果在匹配時出現(xiàn)了
undefined
Tnext[j]?=Tj?，我們就將next[j]更新為next
undefined
[next[j]
undefined
]，直至兩者不相等為止(相當(dāng)于了迭代)。在代碼里面實現(xiàn)就是，如果某個字符已經(jīng)相等或者第一個next[j]數(shù)組值為-1(即
undefined
t=−1)，且主串和模式串指針各后移一位時的字符仍然相同，那么就將當(dāng)前的next[j]值更新為上一個next[j]數(shù)組值，更新后的數(shù)組命名為nextval。
代碼如下：
def getNextval(substrT):
nextval_list = [-1 for i in range(len(substrT))]
j = 0
t = -1
while j < len(substrT) - 1:
if t == -1 or substrT[j] == substrT[t]:
j += 1
t += 1
if substrT[j] != substrT[t]:
# Tj=Tt, 但T(j+1)!=T(t+1), 這個就和next數(shù)組計算時是一樣的
# 可以得到nextval[j+1]=t+1
nextval_list[j] = t
else:
# Tj=Tt, 且T(j+1)==T(t+1), 這個就是next數(shù)組需要更新的
# nextval[j+1]=上一次的nextval_list[t]
nextval_list[j] = nextval_list[t]
else:
# 匹配失敗, 模式串索引為t的字符與當(dāng)前位進行比較
t = nextval_list[t]
return nextval_list
對KMP的優(yōu)化其實就是對next數(shù)組的優(yōu)化，修正后的next數(shù)組，即nextval數(shù)組如下：
| 位編號 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 索引 | 0 | 1 | 2 | 3 | 4 |
| 模式串 | A | A | A | A | B |
| nextval | -1 | -1 | -1 | -1 | 3 |
下面就測試一下：
if __name__ == '__main__':
S1 = 'ABACABAB'
T1 = 'ABAB'
S2 = 'AAABAAAAB'
T2 = 'AAAAB'
print('*' * 50)
print('主串S={0}與模式串T={1}進行匹配'.format(S1, T1))
print('{:*^25}'.format('KMP'))
next_list1 = getNext(T1)
print('next數(shù)組為: {}'.format(next_list1))
index1_1, count1_1 = KMP(S1, T1, next_list1)
print('匹配到的位置(索引): {}, 匹配次數(shù): {}'.format(index1_1, count1_1))
print('{:*^25}'.format('KMP優(yōu)化版'))
nextval_list1 = getNextval(T1)
print('nextval數(shù)組為: {}'.format(nextval_list1))
index1_2, count1_2 = KMP(S1, T1, nextval_list1)
print('匹配到的位置(索引): {}, 匹配次數(shù): {}'.format(index1_2, count1_2))
print('')
print('*' * 50)
print('主串S={0}與模式串T={1}進行匹配'.format(S2, T2))
print('{:*^25}'.format('KMP'))
next_list2 = getNext(T2)
print('next數(shù)組為: {}'.format(next_list2))
index2_1, count2_1 = KMP(S2, T2, next_list2)
print('匹配到的位置(索引): {}, 匹配次數(shù): {}'.format(index2_1, count2_1))
print('{:*^25}'.format('KMP優(yōu)化版'))
nextval_list2 = getNextval(T2)
print('nextval數(shù)組為: {}'.format(nextval_list2))
index2_2, count2_2 = KMP(S2, T2, nextval_list2)
print('匹配到的位置(索引): {}, 匹配次數(shù): {}'.format(index2_2, count2_2))
運行結(jié)果如下：
運行的結(jié)果和我們分析的是一樣的，不修正next數(shù)組時，主串
undefined
S=ABACABAB與模式串
undefined
T=ABAB匹配時需要4次，主串
undefined
S=AAABAAAAB與模式串
undefined
T=AAAAB匹配時需要5次;修正next數(shù)組后，主串
undefined
S=ABACABAB與模式串
undefined
T=ABAB匹配時需要3次，主串
undefined
S=AAABAAAAB與模式串
undefined
T=AAAAB匹配時僅需要2次。
結(jié)束語
在寫本篇博客之前也是反復(fù)看參考書、視頻，邊畫圖邊去理解它，這篇博客也是反復(fù)修改了好幾次，最終算是把KMP解決掉了，有關(guān)字符串知識的復(fù)習(xí)也算是基本結(jié)束，下面就是刷題了(雖然在LeetCode做過了幾道題)。到此這篇關(guān)于Python描述數(shù)據(jù)結(jié)構(gòu)之KMP篇的文章就介紹到這了,更多相關(guān)Python KMP內(nèi)容請搜索服務(wù)器之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持服務(wù)器之家!
原文鏈接：https://blog.csdn.net/qq_42730750/article/details/108058105
