4

2 つの文字列の最長共通部分列については、オンラインで多くの例を見つけました。解決策を理解していると思います。
私が理解できないのは、この問題をN文字列に適用する適切な方法は何ですか? 同じ解決策が何らかの形で適用されていますか? どのように？解決策は異なりますか？何？

4

2 に答える 2

4

入力に任意の数の文字列がある場合、この問題はNP困難になります。この問題は、入力の文字列数が固定されている場合にのみ扱いやすくなります。入力にk個の文字列がある場合、ak次元配列を使用して、サブ問題の保存された最適解に同じDP手法を適用できます。

参照：最長共通部分列問題

于 2012-12-26T19:36:13.033 に答える
1

2 つの文字列 A と B の最長共通部分列 (LCS) を見つけるには、投稿したリンクに示されているように、2 次元配列を斜めにトラバースできます。配列内のすべての要素は、部分文字列 A' および B' の LCS を見つける問題に対応します (A は行番号でカットされ、B は列番号でカットされます)。この問題は、配列内のすべての要素の値を計算することで解決できます。配列要素の値を計算するときは、その値を計算するために必要なすべてのサブ問題が既に解決されていることを確認する必要があります。そのため、2 次元配列を斜めにトラバースします。

このソリューションは、N 個の文字列間の最長の共通サブシーケンスを見つけるようにスケーリングできますが、これには、要素がソリューションを必要とするすべてのサブ問題が解決された場合にのみ任意の要素に到達するように、N 次元の配列を反復する一般的な方法が必要です。

N 次元配列を特別な順序で繰り返す代わりに、問題を再帰的に解くこともできます。再帰では、多くの分岐で同じ中間ソリューションが必要になるため、中間ソリューションを保存することが重要です。私はこれを行う小さな例を書いC#ています:

string lcs(string[] strings)
{
    if (strings.Length == 0)
        return "";
    if (strings.Length == 1)
        return strings[0];
    int max = -1;
    int cacheSize = 1;
    for (int i = 0; i < strings.Length; i++)
    {
        cacheSize *= strings[i].Length;
        if (strings[i].Length > max)
            max = strings[i].Length;
    }
    string[] cache = new string[cacheSize];
    int[] indexes = new int[strings.Length];
    for (int i = 0; i < indexes.Length; i++)
        indexes[i] = strings[i].Length - 1;
    return lcsBack(strings, indexes, cache);
}
string lcsBack(string[] strings, int[] indexes, string[] cache)
{
    for (int i = 0; i < indexes.Length; i++ )
        if (indexes[i] == -1)
            return "";
    bool match = true;
    for (int i = 1; i < indexes.Length; i++)
    {
        if (strings[0][indexes[0]] != strings[i][indexes[i]])
        {
            match = false;
            break;
        }
    }
    if (match)
    {
        int[] newIndexes = new int[indexes.Length];
        for (int i = 0; i < indexes.Length; i++)
            newIndexes[i] = indexes[i] - 1;
        string result = lcsBack(strings, newIndexes, cache) + strings[0][indexes[0]];
        cache[calcCachePos(indexes, strings)] = result;
        return result;
    }
    else
    {
        string[] subStrings = new string[strings.Length];
        for (int i = 0; i < strings.Length; i++)
        {
            if (indexes[i] <= 0)
                subStrings[i] = "";
            else
            {
                int[] newIndexes = new int[indexes.Length];
                for (int j = 0; j < indexes.Length; j++)
                    newIndexes[j] = indexes[j];
                newIndexes[i]--;
                int cachePos = calcCachePos(newIndexes, strings);
                if (cache[cachePos] == null)
                    subStrings[i] = lcsBack(strings, newIndexes, cache);
                else
                    subStrings[i] = cache[cachePos];
            }
        }
        string longestString = "";
        int longestLength = 0;
        for (int i = 0; i < subStrings.Length; i++)
        {
            if (subStrings[i].Length > longestLength)
            {
                longestString = subStrings[i];
                longestLength = longestString.Length;
            }
        }
        cache[calcCachePos(indexes, strings)] = longestString;
        return longestString;
    }
}
int calcCachePos(int[] indexes, string[] strings)
{
    int factor = 1;
    int pos = 0;
    for (int i = 0; i < indexes.Length; i++)
    {
        pos += indexes[i] * factor;
        factor *= strings[i].Length;
    }
    return pos;
}

私のコード例はさらに最適化できます。キャッシュされている文字列の多くは重複しており、一部の文字列は 1 文字だけ追加された重複しています。これは、入力文字列が大きくなると、必要以上のスペースを使用します。

入力時:"666222054263314443712", "5432127413542377777", "6664664565464057425"

返される LCS は"54442"

于 2013-10-19T13:13:50.753 に答える