锐客网

  1. 首页 > it技术 > >

重复子串问题（二）（求一个字符串中连续出现次数最多的子字符串）

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

#include #includeusing namespace std; int con_substr(char *str,char **ret) { int max_time=0; //连续出现的最多次数 int ret_len=0; //连续出现的字符串的长度 char *addr=NULL; //连续出现字符串的起始地址int len=strlen(str); char **a=(char **)malloc(sizeof(char*)*len); //生成后缀数组 for(int i=0; imax_time) { max_time=count; ret_len=i; addr=a[k]; } }} *ret=new char[ret_len+1]; strncpy(*ret,addr,ret_len); (*ret)[ret_len]='\0'; return max_time; }int main() { char str[] = "abcabcabcabcabcabbbb"; char *ret = NULL; int time = con_substr(str, &ret); printf("%s occuers %d times\n", ret, time); }

【重复子串问题（二）（求一个字符串中连续出现次数最多的子字符串）】方法二：利用string类方法实现
#include #include #include using namespace std; pair con_str(const string &str) { vector substrs; int maxcount=1,count=1; string substr; int i,len=str.size(); for(i=0; imaxcount) { maxcount=count; substr=substrs[i].substr(0,j-i); } } } return make_pair(maxcount,substr); }int main() { string str; pair rs; cout<<"Input a string:"<>str) { rs=con_str(str); cout<

    推荐阅读


    上一篇：C++前置式递增++i和后置式递增i++的区别

    下一篇：字符集和字符编码