python数据分组算法（python求解next数组实现KMP算法）

python数据分组算法（python求解next数组实现KMP算法）http://blog.csdn.net/u010189459/article/details/30067705http://www.cnblogs.com/c-cloud/p/3224788.html#!usr/bin/env python #encoding:utf-8 ''' __Author__:沂水寒城 功能：python实现KMP算法 ''' def simple_match_func(one_str two_str): ''' 最简单的字符串匹配算法 ''' length1=len(one_str) length2=len(two_str) for i in range(length1-length2 1): if one_str[i:i length2]==two_str: return True else: return True

今天在做题的时候遇上好几道题目都是有关于KMP字符串匹配中的next数组的相关问题的，这是一个自己的盲区，毕竟之前一直没有看到过，今天就好好研究一下吧，KMP算法的来源，原理我都不多说了，这个是学习数据结构中的经典。

KMP算法，是由Knuth，Morris，Pratt共同提出的模式匹配算法，其对于任何模式和目标序列，都可以在线性时间内完成匹配查找，而不会发生退化，是一个非常优秀的模式匹配算法，KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度O(m n)

看了上面这些简单的介绍不难发现，KMP算法优于简单字符串匹配算法的根本原因就是：引入了一个next数组，这个数组可以尽可能的记录相关的匹配信息，使得在不匹配发生的时候移动的步长不再是固定的一位，加快了匹配进行的速度，在失配后，并不简单地从目标串下一个字符开始新一轮的检测，而是依据在检测之前得到的有用信息即next数组中记录的信息，直接跳过不必要的检测，从而达到一个较高的检测效率，关于它的讲解、实现和优化网上有很多很多的资料，都可以去看看，这里只是简单实现一下，就当做是再学习一次吧，毕竟很久没有使用过了，很多东西都忘记了

下面是具体的实现：

#!usr/bin/env python #encoding:utf-8 ''' __Author__:沂水寒城 功能：python实现KMP算法 ''' def simple_match_func(one_str two_str): ''' 最简单的字符串匹配算法 ''' length1=len(one_str) length2=len(two_str) for i in range(length1-length2 1): if one_str[i:i length2]==two_str: return True else: return True def get_next_group(one_str): ''' 获取到next数组 ''' next_group=[0]*len(one_str) next_group[0]=-1 point=-1 i=0 length=len(one_str) while i<len(one_str)-1: if point==-1 or one_str[i]==one_str[point]: point =1 i =1 next_group[i]=point else: point=next_group[point] return next_group def kmp_match_func(one_str two_str next_group): ''' KMP算法 ''' i=0 j=0 while i<len(one_str) and j<len(two_str): if j==-1 or one_str[i]==two_str[j]: i =1 j =1 else: j=next_group[j] if j==len(two_str): print '模式串在源串中起始位置下标为：' i-j return i-j else: print '匹配失败！！！' return -1 if __name__ == '__main__': flag=simple_match_func('ABCDjfdjkABMFHJKSnvfdj' 'ABM') if flag: print '匹配成功！' else: print '匹配失败！！！' one_str='ABHKjdjfjgkdABBBGNGJJDkfdjkldefervbdfKOPWJ' two_str='ABBBG' one_str='xyxyyxxyx' two_str='xyxyyxxyx' next_group=get_next_group(two_str) print 'next数组为：' next_group start_position=kmp_match_func(one_str two_str next_group) if start_position!=-1: print '模式串为：' one_str[start_position:start_position len(two_str)]

结果如下：

匹配成功！ next数组为： [-1 0 0 0 0] 模式串在源串中起始位置下标为： 12 模式串为： ABBBG [root@server236 one]# python next_group.py 匹配成功！ next数组为： [-1 0 0 1 2 0 1 1 2] 模式串在源串中起始位置下标为： 0 模式串为： xyxyyxxyx

next数组有一个区别就是：有的吧next[0]定义为-1，本文就是这个版本，有的是定义为：0 这个看自己怎么选取了

推荐几个讲解不错的文章：

http://www.cnblogs.com/c-cloud/p/3224788.html

http://blog.csdn.net/u010189459/article/details/30067705