首页 > 代码库 > KMP
KMP
字符串匹配广泛用于各类工程、研究。朴素的字符串匹配像极了两条履带，小的履带先和大的履带对齐，逐个验证上下是否一致。如果不一致，小的履带右移一格，继续上下比对。最坏复杂度是O（nm），实在难以让人满意。
实际上，小履带没必要每次都从头开始和大履带匹配，假设小履带已经匹配了好多，失配后右移一位从头开始走，有一大半点都是和小履带自己在匹配。这不坑爹么，根本没有用到大履带，为何要放到大履带的循环里呢？这部分完全可以做个预处理，下次直接跳到和大履带比对的点就行了。这就是KMP的getfail函数。
void getFail(string str){ f[0]=0;f[1]=0; for(int i=1;i<str.size();i++) { int j=f[i]; while(j&&str[i]!=str[j]) j=f[j]; f[i+1]=(str[i]==str[j]?j+1:0); }}
getfail函数采用类似动态规划的思想，记录每次应该跳跃到的点。
int KMP(string obj,string ask,int pos){ getFail(ask); int j=0; int n=obj.size(); for(int i=pos;i<n;i++) { while(j&&ask[j]!=obj[i]) j=f[j]; if(ask[j]==obj[i]) j++; if(j==ask.size()) { res++; return i-j+1; }}
匹配的时候直接从f记录的点开始，省去不少麻烦。
@练习题
HDU 3336
POJ 1961
KMP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。