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

相关文章

pandas的to_datetime时间转换使用及学习心得

前言 昨天在网赛中做了一道题,虽然是外国人的Englis题目,但是内容很有学习的价值,值得仔细的学习,今天就把我所收获的一部分记录下来。其一:做个学习的资料记录。其二:分享出来,供大家参...

python调用windows api锁定计算机示例

调用Windows API锁定计算机 本来想用Python32直接调用,可是没有发现Python32有Windows API LockWorkStation(); 因此,就直接调用W...

PyTorch学习笔记之回归实战

PyTorch学习笔记之回归实战

本文主要是用PyTorch来实现一个简单的回归任务。 编辑器:spyder 1.引入相应的包及生成伪数据 import torch import torch.nn.functio...

python正则表达式re模块详细介绍

本模块提供了和Perl里的正则表达式类似的功能,不关是正则表达式本身还是被搜索的字符串,都可以是Unicode字符,这点不用担心,python会处理地和Ascii字符一样漂亮。 正则表...

python 调用c语言函数的方法

虽然python是万能的,但是对于某些特殊功能,需要c语言才能完成。这样,就需要用python来调用c的代码了 具体流程: c编写相关函数 ,编译成库 然后在python中加载这些...