KMP字元串比對算法了解

KMP算法

一種字元串比對算法，尋找存在于長字元串中的子串，由Knuth、Morris、Pratt三個同時提出來。

算法的基本思路是：

假設有序列seq(長度為m)和子序列subseq(長度為n)，

首先周遊序列seq，找到subseq[0]第一次出現在seq中的位置k；

然後順次比較subseq[j](0<j<n)與seq[i](k<i<m), 即比較以subseq[0]開頭長度為j的序列subseq[0,j]

和以seq[i-1]結尾長度為j的序列seq[i-j,i](此處之是以選擇用i而不是k來描述seq的片段，是想通過序列片段

而不是單個字元進行移動，繼而減少移動次數)：

若在j==n-1時，每個元素都相等，則定位了一個子序列，重複上面的過程即可找到所有子序列的分布位置，

若對某一特定的j(0<j<n)使得subseq[j] <> seq[i]， 這時則宣告最初找到的k不合意（應該後移），無法繼續

延伸，這時需要調整j的值， 繼而影響到k的值。為了調整後，依然滿足subseq[0,j'] == subseq[i-j',i]，就

要求j'應該滿足subseq[0,j']==subseq[j-j',j]，同時最佳j'應該是滿足這個條件的最大值且j' <> j， 使

得能繼續參與比對的序列最長。當然也存在不能找到合适的j'的情況，這時另j'等于0， 而增加i的值直到再次碰到

subseq[0]。同時，我們可以看到j'的取值隻取決于subseq，是以我們可以提前建構出這樣一個索引數組來指導錯誤比對之後的移動。

索引數組index的建構：

索引數組的建構就是對字元串進行自我掃描的過程，每個值都可以遞歸的由其前一個位的值得出。

假設index[j-1] = k, 隻要index[k] == index[j]，index[j] = index[j-1]+1, 因為index[0,k] = index[j-k,j]， 是以index[0,k+1] == index[j-k, j+1]。若index[k] != index[j]，這時可以回溯到index[index[j-1]，若依然不滿足則遞歸index[index[index[j-1]]，直到滿足或取值為0， 由此得到index數組。

假設seq = 'abaebacddebacdbace', subseq = 'bace'.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

a b a e b a c d d e b  a  c  d  b  a  c  e

b a c e

0 1 2 3

當k=1時，subseq[0] == seq[k],

然後subseq[1] == seq[2], subseq[2] != seq[3], 這時需要調整j的值，使得subseq[0,j']依然等同于

seq[i-j'+1,i], 這就使得j'要滿足使得subseq[0,j]的前j'的字母和後j'個字母完全相同， 由于沒有合适的,

j'取值0，此時繼續增大i的值直到再次在seq裡遇到subseq[0]， 重複以上過程。這個例子比較特殊沒有利用到算法的優勢。

若子序列不存在重複，用KMP算法和用下面的一個bruteforce程式效果應該相差不大, 另外python的find和index在處理字元串時速度也很可觀。

另一個例子是matrix67上的， 大家可過去參考下。

參考：http://www.matrix67.com/blog/archives/115

http://stackoverflow.com/questions/425604/best-way-to-determine-if-a-sequence-is-in-another-sequence-in-python

---------------------------

Bruteforce mathod：

---------------------------

def index(subseq, seq):

'''

index(subseq, seq) -->a list of numbers or -1

Return an index of [subseq] in the [seq].

Or -1 if [subseq] is not a subsequence of [seq].

The time complexity of the algorithm is O(n*m), where

n, m = len(seq), len(subseq).

>>>index('12', '0112')

[2]

>>>index([1,2], [011212])

[2, 4]

>>>index('13', '0112')

-1

'''

i, n, m = -1, len(seq), len(subseq)

index = []

try:

while True:

i = seq.index(subseq[0], i+1, n - m + 1)

if subseq == seq[i:i+m]:

index.append(i)

except ValueError:

return index if len(index) > 0 else -1

def subseqInSeq(subseq, seq):

'''

subseqInSeq(subseq, seq) ---> list or -1

The same as index.

'''

indexList = []

m = len(subseq)

subseqRepla = '*' * m

while subseq[0] in seq:

index = seq.index(subseq[0])

if subseq == seq[index:index+m]:

indexList.append(index)

seq = seq.replace(subseq, subseqRepla, 1)

else:

seq = seq.replace(subseq[0], '*', 1)

return (indexList if len(indexList) > 0 else -1)

def main():

print index('ab', 'abcdab')

print subseqInSeq('ab', 'abcdab')

------------------------------------------------------------

KMP

def compute_prefix_function(p):

m = len(p)

pi = [0] * m

k = 0

for q in range(1, m):

while k > 0 and p[k] != p[q]:

k = pi[k - 1]

if p[k] == p[q]:

k = k + 1

pi[q] = k

return pi

def kmp_matcher(t, p):

n = len(t)

m = len(p)

pi = compute_prefix_function(p)

q = 0

for i in range(n):

while q > 0 and p[q] != t[i]:

q = pi[q - 1]

if p[q] == t[i]:

q = q + 1

if q == m:

return i - m + 1

return -1