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编程中装饰器的使用示例解析

装饰函数和方法 我们先定义两个简单的数学函数,一个用来计算平方和,一个用来计算平方差: # get square sum def square_sum(a, b): return...

Python Pillow.Image 图像保存和参数选择方式

保存时代码如下: figure_corp = figure.crop( (32*rate/2, 32*rate/2, 32-32*rate/2, 32-32*rate/2)) fig...

python socket通信编程实现文件上传代码实例

这篇文章主要介绍了python socket通信编程实现文件上传代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 写一个file...

python lambda表达式在sort函数中的使用详解

1.lambda表达式一般用法 语法: lamda argument:expression example: add = lambda x, y: x+y print(add(10,...

Python如何读取MySQL数据库表数据

Python如何读取MySQL数据库表数据

本文实例为大家分享了Python读取MySQL数据库表数据的具体代码,供大家参考,具体内容如下 环境:Python 3.6 ,Window 64bit 目的:从MySQL数据库读取目标表...