poj-2752(拓展kmp)

时间:2024-05-26 22:36:44

题意:求一个串所有的前后缀字串;

解题思路:kmp和拓展kmp都行,个人感觉拓展kmp更裸一点;

拓展kmp:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map>
#define maxn 500500
using namespace std;
char t[maxn];
char s[maxn];
int exnext[maxn];
int extend[maxn];
int tlen,slen;
map<int,int>m;
void get_next()
{
int i=0,j,po;
exnext[0]=tlen;
while(t[i]==t[i+1]&&i+1<tlen)
i++;
exnext[1]=i;
po=1;
for(i=2;i<tlen;i++)
{
if(exnext[i-po]+i<exnext[po]+po)
exnext[i]=exnext[i-po];
else
{
j=exnext[po]+po-i;
if(j<0)
j=0;
while(i+j<tlen&&t[j]==t[j+i])
j++;
exnext[i]=j;
po=i;
}
}
}
int main()
{
while(cin>>t)
{
tlen=strlen(t);
get_next();
for(int i=tlen-1;i>=0;i--)
{
if(exnext[i]==tlen-i)
cout<<tlen-i<<" ";
}
cout<<endl;
}
}