[Poj2752]Seek the name,Seek the fame

佚名 6年前 (2019-04-17) 随笔 2063人围观抢沙发百度已收录

原题链接：http://poj.org/problem?id=2752

题目大意就是给你一个字符串，然后求出所有前缀与后缀相同的字符串长度

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

可以采用Hash，但是个人认为比较麻烦，于是直接上KMP

正好拿模板提练练KMP，其实只有求nxt数组的那一部分

需要注意的是有多组数据，所以需要判断EOF，而且poj不支持万能头...只好打了基本的几个库

code:

#include<cstring> #include<cstdio>
using namespace std; char s[400010]; int n,p[400010],j; int ans[400010],m; int main(){ while(scanf("%s",s+1)!=EOF){ memset(p,0,sizeof(p)); j=0;m=0; n=strlen(s+1); for(int i=1;i<=n;i++){ while(j&&s[i+1]!=s[j+1]) j=p[j]; if(s[j+1]==s[i+1]) j++; p[i+1]=j; } int now=n; while(p[now]){ ans[++m]=p[now]; now=p[now]; } for(int i=m;i>=1;i--) printf("%d ",ans[i]); printf("%d\n",n); } return 0; }