求一个字符串中连续出现的次数最多的子串。例如字符串“abababc”,最多连续出现的为ab，连续出现三次。要和求一个字符串中的最长重复子串区分开来，还是上面的字符串，那么最长的重复子串为abab。两个题目的解法有些类似，都用到了后缀数组这个数据结构。求一个字符串中连续出现的次数最多的子串，首先生成后缀数组例如上面的字符串为:

abababc

bababc

ababc

babc

abc

bc

c

可以看出第一个后缀数组和第三个后缀数组的起始都为ab，第5个后缀数组也为ab。可以看出规律来，一个字符串s，如果第一次出现在后缀数组i的前面，那么如果它重复出现，下一次出现应该在第i+len(s)个后缀数组的前面。这个规律也不难看出。那么从头到尾按照这个规律搜索下不难得出结果。下面是代码：

1 #include 
     
       2 using namespace std; 3  4 int con_sub(char *str, char **ret); 5  6 int main() 7 { 8         char str[] = "abcabcabcabcabcabbbb"; 9         char *ret = NULL;10         int time = con_sub(str, &ret);11         printf("%s occuers %d times\n", ret, time);12         return 0;13 }14 15 int con_sub(char *str, char **ret)16 {17         int max_time = 0;//连续出现的最多次数18         int ret_len = 0;//连续出现的字符串的长度19         char *addr = NULL;//连续出现字符串的起始地址20 21         int len = strlen(str);22         char **a = (char **)malloc(sizeof(char *)*len);23         //生成后缀数组24         for(int i=0; i
      
        max_time)41                         {42                                 max_time = temp_time;43                                 ret_len = i;44                                 addr = a[k];45                         }46                 }47         }48         *ret = new char[len+1];49         strncpy(*ret, addr, ret_len);50         return max_time;51 }
      
     

 注意：这里有一个小技巧，加入字符串中存在出现次数相同的子串，如何优先选择更长的字符串作为最终的结果？可以调整子串的长度为从大到小。