文档介绍：字符串匹配算法
主讲人:郭鹏飞
武汉光电国家实验室
字符串匹配算法
BF算法(Brute Force)
KMP算法(Knuth-Morris-Pratt)
Horspool算法
Sunday算法
BM算法(Boyer-Moore)
约定
文本串(T):被检索的字符串,查找其中是否有某子字符串
模式串(M):文本串中要检索出的子串
i:文本串中当前参与比较的元素下标
j:模式串中当前参与比较的元素下标
失配:与匹配相反,指T串与M串某位进行比较时出现不相等的情况。
BF算法
原理:首先将文本串和模式串左对齐,然后从左向右一个一个进行比较,如果不成功则模式串向右移动一个单位。
优点:简单易懂,易于实现
缺点:时间复杂度为O(len(T)*len(M))
KMP算法
KMP算法是一个经典的字符串匹配算法。
主要思想是:每当一趟匹配过程中出现失配时,不需回溯i,而是利用已经得到的“部分匹配”的结果将模式串向右滑动尽可能远的距离后继续进行比较。
实例:
KMP算法
算法原理:
当然,也可能正确匹配结果在T[i]之后,此时的位移值s>j,只需要选取位移j+1(s>=j+1)位,此时,也不会滤过正确匹配位移值。
失配后,M串要向右移动。如果移动s(j>=s>0)位后,为正确匹配结果,那么有M[j-1]=M[j-s-1],M[j-2]= M[j-s-2],……, M[s] = M[0],且M[j]!=M[j-s]。以上是正确匹配的必要条件。
根据此必要条件,寻找符合条件的位移大小s。而满足这个必要条件的s可能有多个,那么只需选取其中最小s(最大重复串),这样就不会滤过正确匹配位移值。
KMP算法
失配后最大重复串求法:
Mr[j] = Max{k|k=0 或 0<k<j且’M[0]…..M[k-1]’= ‘M[j-k]…..M[j-1]’} (j >0)
失配后模式串M最小位移求法:
位移大小实际会转换成 j 位置的更换,此处直接使用next[j]来表示M[j]失配后 j 的新值。
KMP算法
算法流程:
1、计算next[j]数组,左对齐T串与M串,i=j=0;
2、从i开始依次比较T[i]与M[j]字符;
3、如果匹配则i、j递增;
4、如果失配,那么:当next[j]=-1时,i++,j=0;当next[j]!=-1时,j=next[j]。转向步骤2。
Horspool算法
原理:
首先将T串与M串左端对齐;
从M串的末位从右到左比较字符;
匹配就继续比较直到比较完成;
失配的情况下,从M串失配的位置起,往左寻找与T串失配字符相等的字符,然后将M串向右移动相应的距离,转移到步骤2;找不到,则将M串左边与失配T[i]字符的下一位对齐,转移到步骤2。
Horspool算法
正确性:失配发生时,M串要向右移动,T串的失配字符T[i]可能是正确结果中的一个元素也可能不是。
如果不是,那么可以将M串的首位与T串中的[i+1] 位对齐,继续进行比较;
如果是,那么,自M串失配位置[ j ] 开始向左的任意一位与M[i] 相等的字符c确定的比较位置都可能是完全匹配的,其产生的位移依次为k1,k2,……(ki为 j – location(c))。
综合这两种情况,选择位移最小值k1,这样就能保证不会错过正确匹配的情况。
优点:这个算法是字符串匹配算法中从右向左匹配的创始者,且其失配情况下不是+1位移,平均时间复杂度为O(len(T))。
缺点:只是用了当前匹配位的特征,没有使用之前比较的历史数据,使得失配后M串位移没有最大化。