3串輸入中最長的公共子串

Question

我正在爲自己的實踐做這個問題，並不確定我是否以最有效的方式進行操作。請分享任何關於提高效率和算法的想法。

我的算法：

• 爲每個相應的字符串3個後綴數組。
• 創建後綴數組：一個遍歷字符串的循環，然後使用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-string，那麼這個算法將不起作用，因爲那樣我就要創建n-suffixArrays。那麼我們通常如何處理這種情況呢？
• 關於我們通常如何解決這類問題（子字符串）的一般想法？

（語言沒有障礙）

Answer 1

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

Answer 2

給三個串A，B，C這樣的算法可以是解決在O（長度的（a）*長度（b）*長度（c））。

下面的算法可以重寫使用DINAMIC編程以提高性能，但它是一個很好的起點：

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