Goto PRoblemSet
Description
俗话说“好命不如好名”，小h准备给他的宠物狗起个新的名字，于是他把一些英文的名字全抄下来了，写成一行长长的字符串，小h觉得一个名字如果是好名字，那么这个名字在这个串中既是前缀，又是后缀，即是这个名字从前面开始可以匹配，从后面开始也可以匹配，例如abc在 abcddabc中既是前缀，也是后缀，而ab就不是，可是长达4*10^5的字符让小h几乎昏过去了，为了给自己的小狗起个好名字，小h向你求救，并且他要求要将所有的好名字的长度都输出来。
Input
一行，要处理的字符串（都是小写字母）。
Output
一行若干个数字，从小到大输出，表示好名字的长度。
Sample Input
abcddabc
Sample Output
3 8
思路：这题是个sb题，可以说几乎是裸的kmp？直接预处理p数组然后判断开头直接是否相同，相同则把个数放在答案里头。
#include<cstdio>#include<cstring>#define F(i,x,y) for(int i=x;i<=y;i++)#define d(i,x,y) for(int i=x;i>=y;i--)using namespace std;const int maxn = 400000 + 50;char s[maxn];int ans[maxn],p[maxn];int len,num = 0;int main(){ scanf("%s",s+1); len = strlen(s+1); int j = 0; F(i,2,len-1) { while(j && s[j+1]!=s[i]) j = p[j]; if(s[j+1]==s[i]) p[i] = j+1; j = p[i]; } p[0] = -1; while(j>=0) { if(s[j+1]==s[len]) num++,ans[num] = j + 1; j = p[j]; } d(i,num,1) printf("%d ",ans[i]); printf("%d/n",len); return 0;}新闻热点
疑难解答
