面試題[後綴數組]: 最長重復子串

面試題[後綴數組]: 最長重復子串

題目：給定一個字符串，求出最長重復子串。

這個題目可以用後綴數組來解：對後綴數組排好序，這樣重復的子串就在相鄰的後綴中找就可以了。我的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;
    }
};