本文主要是介绍最长重复子串—后缀数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
知识点：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;
}这篇关于最长重复子串—后缀数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
