【字元串入門專題1】F - Seek the Name, Seek the Fame poj2752【kmp】

Seek the Name, Seek the Fame

Description

The little cat is so famous, that many couples tramp over hill and dale to Byteland, and asked the little cat to give names to their newly-born babies. They seek the name, and at the same time seek the fame. In order to escape from such boring job, the innovative little cat works out an easy but fantastic algorithm: 

Step1. Connect the father's name and the mother's name, to a new string S. 

Step2. Find a proper prefix-suffix string of S (which is not only the prefix, but also the suffix of S). 

Example: Father='ala', Mother='la', we have S = 'ala'+'la' = 'alala'. Potential prefix-suffix strings of S are {'a', 'ala', 'alala'}. Given the string S, could you help the little cat to write a program to calculate the length of possible prefix-suffix strings of S? (He might thank you by giving your baby a name:) 

Input

The input contains a number of test cases. Each test case occupies a single line that contains the string S described above. 

Restrictions: Only lowercase letters may appear in the input. 1 <= Length of S <= 400000. 

Output

For each test case, output a single line with integer numbers in increasing order, denoting the possible length of the new baby's name.

Sample Input

ababcababababcabab
aaaaa
      

Sample Output

2 4 9 18
1 2 3 4 5      

題意：按從小到大的順序輸出字元串字首和字尾相等的長度.

思路：利用next數組的性質，從後往前滾動查找，因為s[i]必定等于s[next[i]],最後輸出.

這道題真是逾時超到爆炸，去掉判斷語句，沿用小夥伴的方法，自己就a了，真尴尬~~~

超級喜歡遞歸調用輸出，感覺就像黑科技一樣（好像有點誇張了），不用新的數組存值，避開了我數組範圍總是定小的毛病

#include<stdio.h>
#include<string.h>
#define N 510000
char s[N];
int NEXT[N],num[N];

void get_next()
{
	int j,k;
	NEXT[0] = k = -1;
	j = 0;
	while(s[j]!='\0')
	{
		if(k==-1||s[k]==s[j])
			NEXT[++j] = ++k;
		else
			k = NEXT[k];
	}
	
	return;
}

void print(int n)
{
	if(NEXT[n] > 0)
	{
		print(NEXT[n]);
		printf("%d ",NEXT[n]);
	}
}
int main()
{
	int i,j;
	while(scanf("%s",s)!=EOF)
	{
		get_next();
		print(strlen(s));
		printf("%d\n",strlen(s));
	}
	return 0;
}