官方网站建设费用,网站怎么做值班表,票付通app下载,电子商务网站建设模板1. 原由
紧接上文#xff0c;我们知道了暴力匹配的算法在时间运行上的缺陷#xff0c;假设字符串T的长度为n#xff0c;字符串P的长度为m#xff0c;则整个算法的时间复杂度为O( n * m )#xff0c;而对于一个复杂的现实情况而言 n m 2 #xff08;即…1. 原由
紧接上文我们知道了暴力匹配的算法在时间运行上的缺陷假设字符串T的长度为n字符串P的长度为m则整个算法的时间复杂度为O( n * m )而对于一个复杂的现实情况而言 n m 2 即n远远大于mm远远大于常数这样的计算计算机的负担很重。
请思考一个暴力匹配的情况
给定一个主字符串
T “AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB”(47位)
同时给定模式串 P “AAAAAB”6位
试问搜索的情况很显然暴力搜索对于每一次搜索都要搜索到最后一个字符才能进行下一轮的搜索因此进行的计算近似可以理解为O(47 * 6) 对于这样很少的数据已经有很高的计算量了。
KMP算法一种改进的模式匹配算法是D.E.Knuth、V.R.Pratt、J.H.Morris于1977年联合发表KMP算法又称克努特-莫里斯-普拉特操作 KMP算法与前文的暴力匹配算法核心的区别就是没有不匹配的回溯而是根据整个字符串的情况进行一次位移这样大大减少了回溯产生的缺陷KMP算法的时间复杂度可以优化到 O( n m)级别是二次优化到线性的程度。
2.构造next表(以-1开头)
对于模式串P而言我们需要知道模式串中P的每一位的前一位是否存在相等的完全相等的前后缀并且求这个最大的完全相等的前后缀如一个模式串”ABCABDE”对于第倒数第二位字符而言其符合情况的前后缀就是”AB”而最后一位则没有完全相等的前后缀。
PS何为前后缀如一个字符串”ABCD”,其前缀有可能为”A”“AB”“ABC”(即除去本身的全部字符)同理则后缀可能为”D””CD””BCD”
我们需要求的就是每一个字符其相对应的最大前后缀数这样与模式串P一一对应的表称之为next表。
因此”ABCABDE”的next表为-1 0 0 0 1 2 0 字符用空格隔开
那么我们该如何实现代码呢
对于每一个当前需要判断的字符而言在构造next表时应该向前进行比对以上一个已经判断的情况为基础初始值赋-1部分教程中初始值赋0两者没有实质区别后缀如果1位置的字符与前缀1位置的字符相等则next[i]就是next[i-1]1而如果不相等则说明无法匹配则next[i]0。
3. KMP实现
与暴力匹配极其相似利用while循环的条件控制 进行匹配失败时只需要将失败的模式串P的索引指向next表中对应的数值即可其余匹配照旧线性执行即可。
4. 实现代码仅作参考
#includeiostream
#includecstdio
#includecstring
using namespace std;int *buildNext(char *P){int m strlen(P) , j0;int * N new int[m];int t N[0] -1;while( j m-1 ){if( 0 t || P[j] P[t] ){N[j] t;}else{t N[t];}}return N;
}int KMP(char T[],char P[]){ //T--主串,P--模式串int *next buildNext(P); //构造NEXT表int n strlen(T) , i0;int m strlen(P) , j0;while( jm in ){if( j0 || T[i]P[j] ){i;j;}else{j next[j];}}delete []next;return i-j;
}int main(){char org[] ABABABABABD;char str[] ABABD;int ans KMP(org,str);cout ans endl;return 0;
}输出6即经过6位在第七位发生匹配
