连续出现次数最多的子串—后缀数组

本文主要是介绍连续出现次数最多的子串—后缀数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

  http://blog.csdn.net/ysu108/article/details/7795479 讲解

  http://blog.csdn.net/imcdragon/article/details/6838565 代码

  面试宝典P237 源

 
基本算法描述:
例如字符串“abababc”,最多连续出现的为ab，连续出现三次。

要和求一个字符串中的最长重复子串区分开来，还是上面的字符串，那么最长的重复子串为abab。


求一个字符串中连续出现的次数最多的子串，首先生成后缀数组例如上面的字符串为:
abababc
bababc
ababc
babc
abc
bc
c
可以看出第一个后缀数组和第三个后缀数组的起始都为ab，第5个后缀数组也为ab。

可以看出规律来，一个字符串s，如果第一次出现在后缀数组i的前面，那么如果它重复出现，下一次出现应该在第i+len(s)个后缀数组的前面。

这个规律也不难看出。那么从头到尾按照这个规律搜索下不难得出结果

#include <iostream>
#include <string>
#include <vector>
#include <utility>
using namespace std;pair<int, string> fun(const string &str)
{vector<string> substrs;int maxcount = 1, count = 1;string substr;int i, len = str.length();for(i=0; i<len; ++i)/*生成后缀数组*/substrs.push_back(str.substr(i, len-i));		/*for(i=0; i<len; ++i)cout << substrs[i] << endl;*/for(i=0; i<len; ++i){	for(int j=i+1; j<len; ++j){count = 1;//当重复的字符串长度为(j-i)的时候，如果是连续出现的，//那么第j和第j+(j-i),j+2*(j-i)...个后缀数组前面为重复的字符串if(substrs[i].substr(0, j-i) == substrs[j].substr(0,j-i)){++count;for(int k=j+(j-i); k<len; k+=j-i)	{	//如果是连续出现的，那么第j和第j+(j-i),j+2*(j-i)...个后缀数组前面为重复的字符串if (substrs[i].substr(0,j-i) == substrs[k].substr(0, j-i))++count;elsebreak;}if(count > maxcount){maxcount = count;substr=substrs[i].substr(0, j-i);}}}}return make_pair(maxcount, substr);
}int main()
{pair<int, string> rs;string str="abcabcabcabcabcabbbb";rs = fun(str);cout << rs.second<<':'<<rs.first<<'\n';system("pause");return 0;
} 

              

这篇关于连续出现次数最多的子串—后缀数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---