Python字符串匹配算法KMP实例

这篇文章主要介绍了Python字符串匹配算法KMP实现方法,实例分析了Python针对字符串操作的相关技巧,具有一定参考借鉴价值,需要的朋友可以参考下

本文实例讲述了Python字符串匹配算法KMP。分享给大家供大家参考。具体如下：

1. #!/usr/bin/env python 
2. #encoding:utf8 
3. def next(pattern): 
4. p_len = len(pattern) 
5. pos = [-1]*p_len 
6. j = -1 
7. for i in range(1, p_len): 
8. while j > -1 and pattern[j+1] != pattern[i]: 
9. j = pos[j] 
10. if pattern[j+1] == pattern[i]: 
11. j = j + 1 
12. pos[i] = j 
13. return pos 
14. def kmp(ss, pattern): 
15. pos = next(pattern) 
16. ss_len = len(ss) 
17. pattern_len = len(pattern) 
18. j = -1 
19. for i in range(ss_len): 
20. while j > -1 and pattern[j+1] != ss[i]: 
21. j = pos[j] 
22. if pattern[j+1] == ss[i]: 
23. j = j + 1 
24. if j == pattern_len-1: 
25. print 'matched @: %s' % str(i-pattern_len+1) 
26. j = pos[j] 
27. kmp(u'上海自来水来自海上海', u'上海') 

希望本文所述对大家的Python程序设计有所帮助。