复习KMP

KMP刚学的时候,看不懂。

再看,哇!原来是这样!

用的时候,忘了。

为了不再跌倒,我决定,记住吧。。。

在我看来,KMP一般用于字符串匹配时的防超时优化。

他的精髓就是,利用已经匹配的信息,简化这之后的匹配过程。

小试牛刀:P3375 【模板】KMP字符串匹配

#include<iostream>
#include<cstdio>
#include<math.h>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e6+;
int net[N];
char s[N],t[N];
void get_net()
{
int i=,j=;
int len=strlen(t+);
for(;i<=len;i++)
{
while(j&&t[j+]!=t[i]) j=net[j];
if(t[j+]==t[i]) j++;
net[i]=j;
}
}
void match()
{
int lens=strlen(s+),lent=strlen(t+);
for(int i=,j=;i<=lens;i++)
{
while(j&&s[i]!=t[j+]) j=net[j];
if(s[i]==t[j+]) j++;
if(j==lent) printf("%d\n",i-lent+);
}
}
int main()
{
cin>>(s+)>>(t+);
get_net();
match();
int lens=strlen(s+),lent=strlen(t+);
for(int i=;i<=lent;i++)
printf("%d ",net[i]); return ;
}
上一篇:SVN基于Maven的Web项目更新,本地过程详细解释


下一篇:数据库的修改和删除;比较标签代替<,>,=号;模板替换;session的用法