描述

给定一个长度为n的字符串S，如果存在一个字符串T，重复若干次T能够得到S，那么，S叫做周期串，T叫做S的一个周期。
如：abababab是一个周期串，abab，ab都是它的周期，其中,ab为它的最小的周期串。

使用next，线性时间解决问题

k=next[len],p=len-k;
若len%p==0,则p为最小周期长度，前p个字符就是最小周期

若len%p!=0,则字符串不存在周期

这里，我们对next数组多求了一位，即next[len]位。

#include<stdio.h>
#include<string.h>
#include<string>
using namespace std;
int next[100];
void GetNext(char* str)
{
	next[0]=-1;
	int k=-1;
	int j=0;
	int len=strlen(str);
	while(j<len)
	{
		if(k==-1||str[j]==str[k])
		{
			next[j+1]=k+1;
			j++;
			k++;
		}
		else
		{
			k=next[k];
		}
	}
}

int main()
{	
	char str[100];
	while(scanf("%s",str)!=EOF)
	{
		GetNext(str);
		int len=strlen(str);
		int p=len-next[len];
		if(p==len)
		{
			printf("NULL\n");
		}
		else if(len%p==0)
		{
			for(int i=0;i<p;i++)
			{
				printf("%c",str[i]);
			}
			printf("\n");
		}
		else
		{
			printf("NULL\n");
		}
	}
	return 0;
}