Python字符串匹配算法KMP实例

yipeiwu_com5年前Python基础

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

#!/usr/bin/env python
#encoding:utf8
def next(pattern):
p_len = len(pattern)
pos = [-1]*p_len
j = -1
for i in range(1, p_len):
while j > -1 and pattern[j+1] != pattern[i]:
j = pos[j]
if pattern[j+1] == pattern[i]:
j = j + 1
pos[i] = j
return pos
def kmp(ss, pattern):
pos = next(pattern)
ss_len = len(ss)
pattern_len = len(pattern)
j = -1
for i in range(ss_len):
while j > -1 and pattern[j+1] != ss[i]:
j = pos[j]
if pattern[j+1] == ss[i]:
j = j + 1
if j == pattern_len-1:
print 'matched @: %s' % str(i-pattern_len+1)
j = pos[j]
kmp(u'上海自来水来自海上海', u'上海')

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

相关文章

Python3中详解fabfile的编写

fab命令好似结合我们编写的fabfile.py(其它文件名必须添加-f filename应用)来搭配使用的,部分命令行参数可以通过相应的方法来替代,使之更加灵活,例如"-H 192.1...

解决python给列表里添加字典时被最后一个覆盖的问题

如下所示: >>> item={} ; items=[] #先声明一个字典和一个列表,字典用来添加到列表里面 >>> item['index']...

Python中低维数组填充高维数组的实现

Python中低维数组填充高维数组的实现

今天遇到这样一种业务情况: 我的图片的画布是(4,4,3)的三维数组,而得到的图片是(2,2,3)的三维数组,我要把图片放到画布的中间某个位置应该怎么做呢? 大家首先想到是遍历循环,但是...

python实现机器学习之多元线性回归

python实现机器学习之多元线性回归

总体思路与一元线性回归思想一样,现在将数据以矩阵形式进行运算,更加方便。 一元线性回归实现代码 下面是多元线性回归用Python实现的代码: import numpy as np...

使用Python对SQLite数据库操作

SQLite是一种嵌入式数据库,它的数据库就是一个文件。由于SQLite本身是C写的,而且体积很小,所以,经常被集成到各种应用程序中,甚至在IOS和Android的APP中都可以集成。...