首页 > 代码库 > KMP算法
KMP算法
KMP算法是用于处理字符串匹配问题的,在字符串题目中,会遇到匹配问题,如问s1是否是s的子串?
这时我们就要去扫描这两个字符串,如果使用两层循环暴力枚举这个解的话,就会产生O(n*m)的复杂度,n、m是字符串的长度;
我们用较短的字符串去匹配长的字符串,把他放下面
KMP正是优化了这一过程,如果我们从第一位开始枚举时发现下一个字符互不相等,那么我们就要把下面的字符串右移一位,把上面字符串的第二位去匹配下面字符串的第一位,然后第三位匹配下面的第二位……由于我们从下面的第一位开始搜索,这就产生的大量的重复步骤,我们要简化这一步骤,就产生了KMP这种东西
先来一个前缀包含问题
字符串ABCDABCD
前缀:A 、AB、ABC、ABCD、ABCDA、ABCDAB、ABCDABC
其中ABCDABC中有七个字符,
如果我们把它看成一个字符串,而不仅是一个前缀,我们就发现他的前缀ABC和后缀ABC是一毛一样的,我们就可以根据这个东东处理出一个数组next,next[i]存放的就是这个前i个字符前缀和后缀相同的最大前缀的字符数,这里next[7]=3;
根据这个我们在匹配失败时就可以避免从头再来,直接将next复制给相同字符数就可以,确实很方便,但是不好理解,额,其实也是很好理解的,。
至于next的递推和这个过程基本上是一致的很好理解
#include <iostream>#include <cstring>using namespace std;const int n=1000002;int next[n];char s1[n], s2[n];int len1,len2;void getnext(){ int j,k; j=0;k=-1;next[0]=-1; while(j<len2) if(k==-1||s2[j]==s2[k]) next[++j]=++k; else k=next[k];}int address()//返回第一次出现的位置 { int i=0,j=0; getnext(); while(i<len1&&j<len2) { if(j==-1||s1[i]==s2[j]) { i++;j++; } else j=next[j]; } if(j==len2) return i-len2; else return -1;}int count()//返回出现的次数 { int ans=0; int i,j=0; getnext(); for(i=0;i<len1;i++) { while(j>0&&s1[i]!=s2[j]) j=next[j]; if(s1[i]==s2[j]) j++; if(j==len2) { ans++; j=next[j]; } } return ans;}int main(){ int sum; int i; cin>>sum; while(sum--) { cin>>s1>>s2; len1=strlen(s1); len2=strlen(s2); cout<<address()<<endl; cout<<count()<<endl; } return 0;}
KMP算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。