学步园

#include "stdafx.h"
#include <iostream>
using namespace std;
//求一个字符串中连续出现的次数最多的子串。例如字符串“abababc”,最多连续出现的为ab，连续出现三次。
//要和求一个字符串中的最长重复子串区分开来，还是上面的字符串，那么最长的重复子串为abab。两个题目的解法有些类似，
//都用到了后缀数组这个数据结构。求一个字符串中连续出现的次数最多的子串，首先生成后缀数组例如上面的字符串为:
//abababc
//bababc
//ababc
//babc
//abc
//bc
//c
//可以看出第一个后缀数组和第三个后缀数组的起始都为ab，第5个后缀数组也为ab。可以看出规律来，一个字符串s，
//如果第一次出现在后缀数组i的前面，那么如果它重复出现，下一次出现应该在第i+len(s)个后缀数组的前面。
//这个规律也不难看出。那么从头到尾按照这个规律搜索下不难得出结果。
int con_sub(char *str,char *ret)
{
	int max_time=0;//记录最大次数
	int temp_time = 1; 
	int len=strlen(str);
	char** next=(char**)malloc(sizeof(char *)*len);
	for (int i=0;i<len;i++)//后缀数组
	{
		next[i]=str+i;
	}
	for (int k=1;k<(len+1)/2;k++)//对称大小不会大于一半
	{
		for (int i=0;i<len-1;i++)
		{
			int start=i;//指示正在比较的位置
			temp_time=1;
			while ((start+k<=len-1)&&strncmp(next[start],next[start+k],k)==0)//跨度为k进行比较前k个字符
			{
                 start+=k;
				 temp_time++;
			}
		   if (temp_time>max_time)
		   {
			   max_time=temp_time;
			   strncpy(ret,str+i,max_time*k);//把最大的对称字符串保存起来
		   }
		}
	} 
   return max_time;
}