python实现BM和KMP算法

cucugbgb

1.KMP算法

1. 
   
2. def compute_prefix_function(p):
   
3.     m = len(p)
   
4.     pi = [0] * m
   
5.     k = 0
   
6.     for q in range(1, m):
   
7.         while k > 0 and p[k] != p[q]:
   
8.             k = pi[k - 1]
   
9.         if p[k] == p[q]:
   
10.             k = k + 1
    
11.         pi[q] = k
    
12.     return pi
    
13. 
    
14. def kmp_matcher(t, p):
    
15.     n = len(t)
    
16.     m = len(p)
    
17.     pi = compute_prefix_function(p)
    
18.     q = 0
    
19.     for i in range(n):
    
20.         while q > 0 and p[q] != t[i]:
    
21.             q = pi[q - 1]
    
22.         if p[q] == t[i]:
    
23.             q = q + 1
    
24.         if q == m:
    
25.             return i - m + 1
    
26.     return -1

复制代码

2.BM算法例子

1. ef BoyerMooreHorspool(pattern, text):
   
2.     m = len(pattern)
   
3.     n = len(text)
   
4.     if m > n: return -1
   
5.     skip = []
   
6.     for k in range(256): skip.append(m)
   
7.     for k in range(m - 1): skip[ord(pattern[k])] = m - k - 1
   
8.     skip = tuple(skip)
   
9.     k = m - 1
   
10.     while k < n:
    
11.         j = m - 1; i = k
    
12.         while j >= 0 and text[i] == pattern[j]:
    
13.             j -= 1; i -= 1
    
14.         if j == -1: return i + 1
    
15.         k += skip[ord(text[k])]
    
16.     return -1
    
17. 
    
18. if __name__ == '__main__':
    
19.     text = "this is the string to search in"
    
20.     pattern = "the"
    
21.     s = BoyerMooreHorspool(pattern, text)
    
22.     print 'Text:',text
    
23.     print 'Pattern:',pattern
    
24.     if s > -1:
    
25.         print 'Pattern \"' + pattern + '\" found at position',s
    

复制代码

这两个算法主要应用于字符串匹配。

beyond_touch

更喜欢你把paper也发出来