首页 > 代码库 > 字符串的模式匹配——Brute-Force算法和KMP算法
字符串的模式匹配——Brute-Force算法和KMP算法
子串的定位操作是要在主串S中找出一个与子串T相同的子串，通常把主串S称为目标，把子串T称为模式
把从目标S中查找模式为T的子串的过程称为“模式匹配”。
1.Brute-Force算法的设计思想
Brute-Force是普通的模式匹配算法。将主串S的第1个字符和模式T的第1个字符比较，若相等，继续逐个比较后续字符；若不等，从主串的下一字符起，重新与模式的第一个字符比较，直到主串的一个连续子串字符序列与模式相等 ，返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功；否则，匹配失败，返回值 0。
def index(text,tgt_str): j=0 tgt_len=len(tgt_str) for i in range(len(text)): if( text[i] == tgt_str[j] ): j+=1 else: i=i-j+1 j=0 if(j==tgt_len): return i-tgt_len+1 return 0
2.Brute-Force算法的特点：
每次遇到匹配不成功的情况，指针i都要移到本次匹配的开始位置的下一位，称这样的指针移动为回溯
指针的回溯越多，简单模式匹配的执行次数越多
Brute-Force匹配算法的最坏时间复杂度为 O(n*m)
一般情况下BF算法的时间复杂度为O(n+m)
3.KMP算法的改进
每当一趟匹配过程中出现字符比较不等时，不需回溯指针i，而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远的一段距离后，继续比较
KMP算法的时间复杂度可以达到O(m+n)
4.KMP算法的设计思想
假设以指针 i 和 j 分别指示主串和模式中正待比较的字符，令 i 的初值为0，j 的初值为0
若在匹配过程中，Si=Pj，则i和j分别增1，否则i不变，而j退到next[j]的位置再比较，若相等，则指针各自增1，否则j再退到下一个next值的位置，依次类推
若令next[j]=k，则next[j]表明当模式中第j个字符与主串中相应字符失配时，在模式中需重新和主串中该字符进行比较的字符的位置
模式串的next函数定义为
#coding=utf-8str1=‘9AA8‘text=‘8149AA86A5482A12958509AA8‘nextList=[0]def get_next(tgt_str): i=1;j=0 global nextList while(i < len(tgt_str)): if(j == 0 or tgt_str[i-1]==tgt_str[j-1]): i+=1;j+=1 nextList.append(j) else: j=nextList[j-1] return nextListdef Index_KMP(text,tgt_str): j=0 a=len(text) b=len(tgt_str) for i in range(a): while j>0 and text[i]!=tgt_str[j]: j=nextList[j-1] #模式串向右移动 if( text[i] == tgt_str[j] ): j+=1 if j==b: print ‘success‘ print ‘location: ‘+str(i-b+1) j = nextList[j-1] else: print ‘no match‘get_next(str1)print nextListIndex_KMP(text,str1)
字符串的模式匹配——Brute-Force算法和KMP算法