/imcdragon/article/details/6838565解答二
/icyday315/item/040aadab454c8a97151073da合并思路(不能重复abcdabcd 就不行了,abcda是最长重复子串)
/* Author:Mcdragon Date:15-07-1121:17 Description:求一个字符串中连续出现次数最多的子串. 基本算法描述: 给出一个字符串abababa 1.穷举出所有的后缀子串 substrs[0]=abababa; substrs[1]=bababa; substrs[2]=ababa; substrs[3]=baba; substrs[4]=aba; substrs[5]=ba; substrs[6]=a; 2.然后进行比较 substrs[0]比substrs[1]多了一个字母,如果说存在连续匹配的字符,那么 substrs[0]的第1个字母要跟substrs[1]首字母匹配,同理 substrs[0]的前2个字母要跟substrs[2]的前2个字母匹配(否则不能叫连续匹配) substrs[0]的前n个字母要跟substrs[n]的前n个字母匹配. 如果匹配的并记下匹配次数.如此可以求得最长连续匹配子串. */
这个题目不是编程珠玑上看到的,但是解法用到的数据结构在编程珠玑上有讲到,先归类到这里。
求一个字符串中连续出现的次数最多的子串。例如字符串“abababc”,最多连续出现的为ab,连续出现三次。要和求一个字符串中的最长重复子串区分开来,还是上面的字符串,那么最长的重复子串为abab。两个题目的解法有些类似,都用到了后缀数组这个数据结构。求一个字符串中连续出现的次数最多的子串,首先生成后缀数组例如上面的字符串为:
abababc
bababc
ababc
babc
abc
bc
c
可以看出第一个后缀数组和第三个后缀数组的起始都为ab,第5个后缀数组也为ab。可以看出规律来,一个字符串s,如果第一次出现在后缀数组i的前面,那么如果它重复出现,下一次出现应该在第i+len(s)个后缀数组的前面。这个规律也不难看出。那么从头到尾按照这个规律搜索下不难得出结果。下面是代码:
[cpp]