Python字符串匹配算法KMP实例

yipeiwu_com6年前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程序设计有所帮助。

相关文章

使用Python写一个贪吃蛇游戏实例代码

我在程序中加入了分数显示,三种特殊食物,将贪吃蛇的游戏逻辑写到了SnakeGame的类中,而不是在Snake类中。 特殊食物: 1.绿色:普通,吃了增加体型 2.红色:吃了减少体型 3....

tensorflow识别自己手写数字

tensorflow识别自己手写数字

tensorflow作为google开源的项目,现在赶超了caffe,好像成为最受欢迎的深度学习框架。确实在编写的时候更能感受到代码的真实存在,这点和caffe不同,caffe通过编写配...

python协程之动态添加任务的方法

python协程之动态添加任务的方法

python协程只能运行在事件循环中,但是一旦事件循环运行,又会阻塞当前任务。所以只能在当前进程中再开一个线程,这个线程的主要任务是运行事件循环,就是event_loop,因为他是一个无...

python合并文本文件示例

python实现两个文本合并 employee文件中记录了工号和姓名复制代码 代码如下:cat employee.txt:100 Jason Smith200 John Doe300 S...

Python实现购物评论文本情感分析操作【基于中文文本挖掘库snownlp】

Python实现购物评论文本情感分析操作【基于中文文本挖掘库snownlp】

本文实例讲述了Python实现购物评论文本情感分析操作。分享给大家供大家参考,具体如下: 昨晚上发现了snownlp这个库,很开心。先说说我开心的原因。我本科毕业设计做的是文本挖掘,用R...