1

私は自分の練習のためにこの質問をしていますが、最も効率的な方法で行っているかどうかはわかりません. 効率と私のアルゴリズムを改善するためのアイデアを共有してください。

私のアルゴリズム:

  • 対応する文字列ごとに 3 つのサフィックス配列を作成します。
  • 接尾辞配列の作成: 文字列をトラバースし、その後 stl ライブラリを使用してベクトルを並べ替えるための 1 つのループなので、この文字列の前処理は O(n*nlogn) であると思います。(ここで複雑さを軽減するにはどうすればよいですか?)
  • 次に、任意のベクトルをトラバースし、3 つの入力文字列すべてのサフィックス文字列を比較して、最大値と比較します。

コード： 

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 を前処理している部分の複雑さを軽減するにはどうすればよいですか?
  • これは 3 つの文字列の場合ですが、問題のサイズが n 文字列に増加した場合、n-suffixArray を作成する必要があるため、このアルゴリズムは機能しません。では、通常、そのケースをどのように処理しますか?
  • このタイプの質問（部分文字列）を解決するために通常どのように取り組んでいるかについての一般的な考えは?

（言葉の壁はありません）

4

2 に答える 2

0

一般化されたサフィックス配列を使用して、k 共通部分文字列の問題を解決できます

于 2013-09-22T21:54:58.160 に答える
0

3 つの文字列 a、b、c を与えると、このようなアルゴリズムは O(長さ (a) * 長さ (b) * 長さ (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 に答える