string - 3个字符串输入中的最长公共(public)子串

Question

我正在为自己的练习做这道题，但不确定我是否以最有效的方式做。请分享关于提高效率和我的算法的任何想法。

我的算法:

• 为每个对应的字符串创建三个后缀数组。
• 创建后缀数组:一个循环遍历字符串，然后使用 STL 库对向量进行排序，因此我相信这种字符串预处理是 O(n*nlogn)。 (我应该如何降低这里的复杂性？)
• 然后遍历任意向量，比较所有三个输入字符串的后缀字符串，并与你得到的最大值进行比较。

代码:

string commonLongestSubstring(string str1, string str2, string str3)
{
    int length1 = str1.length(), length2 = str2.length(), length3 = str3.length();
    if (length1 == 0 || length2 == 0 || length3 == 0)
        return "";

    vector<string> suffixArray1 = getSuffixArray(str1);
    vector<string> suffixArray2 = getSuffixArray(str2);
    vector<string> suffixArray3 = getSuffixArray(str3);

    string longestCommon = "";  
    for (int i = 0; i < suffixArray1.size() && i < suffixArray2.size() && i < suffixArray3.size(); ++i) {
        string prefix = commonPrefix(suffixArray1[i], suffixArray2[i], suffixArray3[i]);
        if (longestCommon.length() < prefix.length())
            longestCommon = prefix;
    }

    return longestCommon;
}    

string commonPrefix(string a, string b, string c)
{
    string prefix;
    for (int i = 0; i < a.length() && i < b.length() && i < c.length(); ++i) {
        if (a[i] != b[i] || a[i] != c[i])
            break;
        prefix = prefix + a[i];
    }

    return prefix;
} 

vector<string> getSuffixArray(string str)
{
    int length = str.length();
    vector<string> suffixesContainer;

    for (int i = 0; i < length; ++i) {
        suffixesContainer.push_back(str.substr(i, length));
    }

    sort(suffixesContainer.begin(), suffixesContainer.end());

    return suffixesContainer;
}

疑问:

• 如何降低预处理 suffixArray 部分的复杂性？
• 这是针对三个字符串的，但是如果问题大小增加到 n 个字符串，那么这个算法将不起作用，因为那时我必须创建 n 个后缀数组。那么我们通常如何处理这种情况？
• 关于我们通常如何解决此类问题(子字符串)的一般想法？

(语言无障碍)

Answer 1

您可以使用 generalized suffix array解决k-common substring problem