面试题[后缀数组]: 最长重复子串

题目：给定一个字符串，求出最长重复子串。

这个题目可以用后缀数组来解：对后缀数组排好序，这样重复的子串就在相邻的后缀中找就可以了。我的C++代码实现如下：

class Solution
{
public:
    string LongestRepeatingSubstring(string str)
    {
        size_t len = str.size();
        vector
   
     SuffixArray(len); for (size_t i = 0; i < len; ++i) SuffixArray[i] = str.substr(i); sort(SuffixArray.begin(), SuffixArray.end()); size_t maxLen = 0, idx = 0; for (size_t i = 0; i < len - 1; ++i) { size_t curLen = LongestPrefix(SuffixArray[i], SuffixArray[i + 1]); if (curLen >





 maxLen) { maxLen = curLen; idx = i; } } return SuffixArray[idx].substr(0, maxLen); } private: size_t LongestPrefix(string str1, string str2) { size_t len = min(str1.size(), str2.size()); for (size_t i = 0; i < len; ++i) if (str1[i] != str2[i]) return i; return len; } };