KMP刚学的时候,看不懂。
再看,哇!原来是这样!
用的时候,忘了。
为了不再跌倒,我决定,记住吧。。。
在我看来,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 ;
}