首页 > 代码库 > 最长重复子串（转）
最长重复子串（转）
预备知识：
1. sort 使用时得注明：using namespace std; 或直接打 std::sort() 还得加上 #include <algorithm>
2. qort是qsort的升级版，如果能用sort尽量用sort，使用也比较简单，不像qsort还得自己去写 cmp 函数，
只要注明 使用的库函数就可以使用，参数只有两个（如果是普通用法）头指针和尾指针；
3. 默认sort排序后是升序，如果想让他降序排列，可以使用自己编的cmp函数
bool compare(int a,int b){
return a>b; //降序排列，如果改为return a<b，则为升序
}
sort(*a,*b,cmp);
4. compare 函数中对于double需要特别注意返回值的问题，
显然cmp返回的是一个整型，所以避免double返回小数而被丢失。
int cmp( const void *a , const void *b ){
return *(double *)a > *(double *)b ? 1 : -1;
}
分析：要求输出它及其首字符的位置。 例如字符串yyabcdabjcabceg，输出结果应该是abc和3。
1.可以将上面字符串分解为，后缀数组形式。
substrs[0] =yyabcdabjcabceg;
substrs[1] =yabcdabjcabceg;
substrs[2] =abcdabjcabceg;
substrs[3] =bcdabjcabceg;
substrs[4] =cdabjcabceg;
substrs[5] =dabjcabceg;
substrs[6] =abjcabceg;
substrs[7] =bjcabceg;
substrs[8] =jcabceg;
substrs[9] =cabceg;
substrs[10]=abceg;
substrs[11]=bceg;
substrs[12]=ceg;
substrs[13]=eg;
substrs[14]=g;
2.对这些字符串按照字典顺序排序，
3.然后比较相邻字符串的前驱，找到最长的匹配项。
#include <iostream>#include <string>#include <vector>#include <algorithm>using namespace std;pair<int, string> fun(const string &str){ vector<string> substrs; int maxcount = 1; unsigned int count = 0; string substr; int i, len = str.length(); for (i = 0; i < len; i++) // 得到所有的后缀子串 { // basic_string substr(size_type pos = 0,size_type n = npos) const; // 从pos开始，截取n个字符组成的字符串。 substrs.push_back(str.substr(i, len-i)); } // 后缀树排序 sort(substrs.begin(), substrs.end()); // 比较相邻两个字符串公共序列 string str1; string str2; vector<string>::iterator iter; for(iter = substrs.begin(); iter != substrs.end()-1; ){ count = 0; str1 = *iter++; str2 = *iter; while( count < str1.length() && count < str2.length() && (str1.at(count) == str2.at(count)) ) count++; if(count > maxcount){ maxcount = count; substr = str1.substr(0, maxcount); } } substrs.clear(); return make_pair(maxcount,substr);}int main(){ string str; pair<int, string> rs; while (cin >> str) { rs = fun(str); cout << rs.second << ‘:‘ << rs.first << endl; } return 0;}
下面是另一种解题思路：
时间复杂度比上面介绍的要高，但是空间复杂度为O(1).时间换空间。
思路：对源字符串所有后缀的所有子串，从每一个后缀的最长子串开始，
分别从前向和后向开始在源字符串中查找匹配的子串，
若两次查找位置不一致则说明存在重复的长度最长的字串，并返回前向查找时的位置。
e.g. string = “abcedfghiabckl‘，当使用子串”abc“在源字符串中分别前向和后向匹配时，
找到的位置分别为pos1=0， pos2 = 9.
#include <iostream>#include <string>using namespace std;int main(){ string str,tep; cin>>str; cout<<"length=="<<str.length()<<endl; for (int i = str.length()-1; i>=1; i--) { for (int j = 0; j < str.length(); j++) { // 如果没有这句的约束，那么结果错误。 // 这句话使得每次得到的tep的长度是i，即满足从大到小取字符串。 if (j + i <= str.length()) { size_t t = 0; size_t num = 0; tep = str.substr(j, i); // 从大到小取字串。i是截取的字符串的长度，先截取最长的，再截取次长的 t = str.find(tep); // 正序查找 num = str.rfind(tep); // 逆序查找 // 如果两次查找的位置不一样，说明存在重复字串。 if (t != num) // 满足条件就输出，因为是从最长的字符串开始截取。 { cout<<tep<<" "<<t<<endl; return 0; } } } } return 0;}