注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

kmp匹配  

2016-08-07 10:52:57|  分类: 算法&数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数,函数本身包含了模式串的局部匹配信息。
又称看毛片算法233。
===============================
kmp裸题:
给定字符串S和T,求T在S中出现了几次。(nhoi2015T4)
比如S=ABABA,T=ABA,answer=2。
===============================
下述文字会很生硬,yhf已经用尽量简洁易懂的语言表述,希望看一句能理解yhf想表达的意思。字符串都从1开始始始始始始始……
===============================
这次kmp是钟神跟我们讲的,听着听着就懂了一点点。按照yhf的理解,在kmp算法中,在比到s[i]时,kmp在匹配失败时,可以立刻匹配到尽量接近的匹配。也就是尽量接着上次的来,比如这个:
kmp匹配 - 杨鸿飞 - 杨鸿飞的博客
 
你会发现,这次匹配的总是上次匹配的字符串的前缀和后缀(既是前缀也是后缀T[1~x]=T[i-x+1~i](x尽量大)),且是最尽量长且相等。
然后你会发现能匹配的长度(比如第一次,好不容易匹配到了第5位,可是不成功!)越来越短,这样有一个好处,就是上面所说的匹配到尽量接近的匹配
为什么会这样呢?因为你知道,上次匹配了四位,也就是T[1~4]=S[i-4~i-1],然而下次匹配的是T[1~4]的后缀,那也肯定和S[1~i]的后缀(和T[1~4]的后缀长度相等)相等,而T[1~4]的后缀又是前缀,所以就可以跳过去。(只能是这样,其他的后缀只要不是和前缀相同,就无法做到上述的除了第i位不同,其他都相同(只是长度随着跳的次数变短了,也就是更有希望匹配成功))啊!kmp匹配失败时的以“跳”来节省时间就讲到这里。
用k代表当前已匹配的长度(只用知道长度就可以了,这就是kmp的强大)
如果匹配成功,i就往前一格,匹配长度k+1。当k=T.size()时,匹配成功!匹配失败时,k会减少(下文的k=next[k]),也有可能到0,上图就是一个例子,然而当k等于0时,你还指望“跳”吗。
================================
前面说了,我们要知道每一个i的x是多少定义next[i]=x(用途很大,看了上面就知道了,这其实是跳一次后还能匹配的长度)T[1~x]=T[i-x+1~i](x尽量大)。这怎么求呢?还是那张图:
kmp匹配 - 杨鸿飞 - 杨鸿飞的博客
你会发现这总是拿S的后缀和T尽量比较。唉,那不就拿T和T自己匹配一次就行了,然而需要错位,不能从1开始匹配(不然就一次成功啦),所以next[1]=0(x≠i),模拟一次,见表:
 i k(next[i]=k) 过程
 0 0 初始化(第0位等于0起到sb的作用)
 1 0 初始化
 2 0 t[k+1]!=s[i],k=0(continue)
 3 1 t[k+1]==s[i],k++
 4 2 t[k+1]==s[i],k++
 5 0 t[k+1]!=s[i],k=next[k],k=0(continue)
   
这下终于能把kmp的做法将出来了,呼~。然而这是和匹配S是一样的,然后解决一些疑难。
1,求next的时候,k<i。因为被错位了,所以匹配的长度不可能等于i,然而i之前的next都计算过了所以就可以用了。
2,关于k和next的关系就在上文的前缀后缀那儿,这里比较难啃,希望能消化消化再骂yhf。
3,看程序吧,其实只是五行代码。
4,希望看懂后能自己写一下总结,这样能透彻一点。
5,关于时间复杂度,其中k的跳跃看起来是没有规律的,一下子减去很多,而每次最多加1,那当k等于0时,就减不了了。最坏情况就是减一下加一下那也是n。加着加着一下子减完了,那还省去了一个一个减的时间。
================================

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>

using namespace std;

const int MLt=10000;

string S,T;

int next[MLt+10],k;

int main()
{
ios::sync_with_stdio(false);

int t; cin>>t;

for ( ; t>0; t--)
{
cin>>T>>S;

int lens=S.size(),lent=T.size();

S="@"+S; T="$"+T; //以防万一

//memset(next,0,sizeof next); //不用

next[0]=next[1]=k=0; //初始化

for (int i=2; i<=lent; i++)
{
for ( ; k>0/*很重要!!*/ && T[k+1]!=T[i]; k=next[k]);
//失配时的跳跃
if (T[k+1]==T[i]) k++; //匹配成功

next[i]=k;
}

int cnt=0; //count

k=0; //记得清零哦

for (int i=1; i<=lens; i++)
{
for ( ; k>0/*很重要!!*/ && T[k+1]!=S[i]; k=next[k]);
//失配时的跳跃
if (T[k+1]==S[i]) k++; //匹配成功

if (k==lent) { k=next[k]; cnt++; } //找到了一个 !!
}

cout<<cnt<<endl;
}

return 0;
}



 
 

  评论这张
 
阅读(23)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018