Goto PRoblemSet
Description
俗話說“好命不如好名”，小h準(zhǔn)備給他的寵物狗起個新的名字，于是他把一些英文的名字全抄下來了，寫成一行長長的字符串，小h覺得一個名字如果是好名字，那么這個名字在這個串中既是前綴，又是后綴，即是這個名字從前面開始可以匹配，從后面開始也可以匹配，例如abc在 abcddabc中既是前綴，也是后綴，而ab就不是，可是長達(dá)4*10^5的字符讓小h幾乎昏過去了，為了給自己的小狗起個好名字，小h向你求救，并且他要求要將所有的好名字的長度都輸出來。
Input
一行，要處理的字符串（都是小寫字母）。
Output
一行若干個數(shù)字，從小到大輸出，表示好名字的長度。
Sample Input
abcddabc
Sample Output
3 8
思路：這題是個sb題，可以說幾乎是裸的kmp？直接預(yù)處理p數(shù)組然后判斷開頭直接是否相同，相同則把個數(shù)放在答案里頭。
#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;}新聞熱點
疑難解答
