求一个字符串中连续出现的次数最多的子串

布满荆棘的人生 2022-08-03 05:26 368阅读 0赞

求一个字符串中连续出现的次数最多的子串。例如字符串“abababc”,最多连续出现的为ab，连续出现三次。要和求一个字符串中的最长重复子串区分开来，还是上面的字符串，那么最长的重复子串为abab。两个题目的解法有些类似，都用到了后缀数组这个数据结构。求一个字符串中连续出现的次数最多的子串，首先生成后缀数组例如上面的字符串为:  
abababc  
bababc  
ababc  
babc  
abc  
bc  
c  
可以看出第一个后缀数组和第三个后缀数组的起始都为ab，第5个后缀数组也为ab。可以看出规律来，一个字符串s，如果第一次出现在后缀数组i的前面，那么如果它重复出现，下一次出现应该在第i+len(s)个后缀数组的前面。这个规律也不难看出。那么从头到尾按照这个规律搜索下不难得出结果。下面是代码：

**\[cpp\]** [view plain][] [copy][view plain]

1.  \#include <iostream>
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<len; i++) 
25.  a\[i\] = &str\[i\]; 
26. 
27. //重复字符串的长度范围为1到(len+1)/2
28. **for**(**int** i=1; i<=(len+1)/2; i++) 
29.  \{ 
30. //当重复的字符串长度为i的时候，如果是连续出现的，那么第j和第j+i个后缀数组前面为重复的字符串
31. **for**(**int** j=0; j+i<=len-1; j+=i) 
32.  \{ 
33. **int** k = j; 
34. **int** temp\_time = 1; 
35. **while**(k+i <= len-1 && strncmp(a\[k\], a\[k+i\], i) == 0) 
36.  \{ 
37.  temp\_time++; 
38.  k += i; 
39.  \} 
40. **if**(temp\_time > 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. \} 
52.

[view plain]: http://blog.csdn.net/ysu108/article/details/7795479#