学步园

http://blog.csdn.net/huang12315/article/details/6455090

int getNext(char *str,int *next)
{
	int len=strlen(str);
	int index=0;
	int k=-1;
	next[0]=k;
	int max=0;

	//kmp算法求next值，取得最大的字串
	while (index<len)
	{
		if (k==-1 || str[index]==str[k])
		{
			k++;
			index++;
			next[index]=k;
			if (k>max)//求得其中重复最大的字串的个数，也就是与最前面串的重复数
			{
				max=k;
			}
		}
		else
			k=next[k];
	}

	return max;
}

int main()
{
	char str[50];//输入字符串
	cin>>str;
	int max=0;//最大的字串
	int nextMax;//接受getNext函数中返回的最大值
	int index;
	int maxIndex;//保存最大的字串起始位置
	int len=strlen(str);
	//将一个字符串从开始一直减少到只剩一个字符，通过这个取得最小字串
	for (index=0;index<len-1;index++)
	{
		int *next=new int[len-index];//取得next在这没用
		nextMax=getNext(str+index,next);//每次从str+index开始
		if (nextMax>max)
		{
			max=nextMax;
			maxIndex=index;
		}
	}
	
	//输出最长字串
	cout<<"最长字串： ";
	for (index=0;index<max;index++)
	{
		cout<<str[index+maxIndex];
	}
	cout<<endl;
	
	return 0;
}

通过将一个字符串分成n-1个子串，每次通过kmp算法取得字串的next值，从而算出该子串的最长重复子串，保存最大的，就可得答案

其中getNext函数只能取得的是这个子串中后面的子串与开始子串的重复数，所以通过这个思路将一个长的字符串分解为n-1个子串即可