1

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

我的算法：

  • 为每个对应的字符串创建三个后缀数组。
  • 创建后缀数组：一个循环遍历字符串，然后使用 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 后缀数组。那么我们通常如何处理这种情况呢？
  • 关于我们通常如何解决此类问题（子字符串）的一般想法？

（语言无障碍）

4

2 回答 2

0

您可以使用广义后缀数组来解决k-common substring 问题

于 2013-09-22T21:54:58.160 回答
0

给三个字符串 a,b,c 这样的算法可以在 O(length(a) * length(b) * length(c)) 中求解。

可以使用动态编程重写以下算法以提高性能，但这是一个很好的起点：

public static void main(final String[] args) {
    System.out.println(lcs("hello", "othello", "helicopter"));
}

private static String lcs(final String a, final String b, final String c) {
    return recursive_lcs(a, b, c, "");
}

private static String recursive_lcs(final String a, final String b,
        final String c, String res) {
    // Base case: one of the string is empty
    if ((a.length() == 0) || (b.length() == 0) || (c.length() == 0)) {
        return res;
    }
    // Recursive case: find one common character
    else if ((a.charAt(0) == b.charAt(0)) && (b.charAt(0) == c.charAt(0))) {
        res += a.charAt(0);
        // Go to the next character
        final String r1 = recursive_lcs(a.substring(1), b.substring(1),
                c.substring(1), res);
        // Search if exists a longer sequence
        final String r2 = findMax(a, b, c, "");

        if (r2.length() > r1.length()) {
            return r2;
        } else {
            return r1;
        }
    }
    // Recursive case: no common character.
    else {
        // Check if is better the computed sequence, or if exists one better
        // forward
        final String c1 = findMax(a, b, c, "");
        if (c1.length() > res.length()) {
            return c1;
        } else {
            return res;
        }
    }
}

private static String findMax(final String a, final String b,
        final String c, final String res) {
    // Check all the possible combinations
    final String c1 = recursive_lcs(a, b, c.substring(1), res);
    final String c2 = recursive_lcs(a, b.substring(1), c, res);
    final String c3 = recursive_lcs(a.substring(1), b, c, res);
    if (c1.length() > c2.length()) {
        if (c1.length() > c3.length()) {
            return c1;
        } else {
            return c3;
        }
    } else {
        if (c2.length() > c3.length()) {
            return c2;
        } else {
            return c3;
        }
    }
}

输出：

hel
于 2013-09-22T23:16:43.217 回答