c# - LCS 算法 : How to find out from a Table, 找到多少个最长公共(public)子序列？

Question

我用 C# 实现最长公共(public)子序列问题。我需要检测两个字符串之间的所有常见的最大子序列。

为此，我使用 Needleman-Wunsch algorithm 创建了一个表为计算的每一步存储 LCS 序列。

是否有机会确定找到了多少最大子序列(使用表格)？

据此我想选择一种方法来收集每个子序列。重点是，一个子序列不需要递归，因此它会提供更好的性能。这对我的任务至关重要。

这是一个代码片段，其中实现了项目的基本功能:

    private static int[][] GetMatrixLCS(string x, string y)
        {
            var lenX = x.Length;
            var lenY = y.Length;
            matrixLCS = new int[lenX + 1][];
            for (var i = 0; i < matrixLCS.Length; i++)
            {
                matrixLCS[i] = new int[lenY + 1];
            }
            for (int i = 0; i <= lenX; i++)
            {
                for (int j = 0; j <= lenY; j++)
                {
                    if (i == 0 || j == 0)
                        matrixLCS[i][j] = 0;
                    else
                    if (x[i - 1] == y[j - 1])
                        matrixLCS[i][j] = matrixLCS[i - 1][j - 1] + 1;
                    else
                        matrixLCS[i][j] = Math.Max(matrixLCS[i - 1][j], matrixLCS[i][j - 1]);
                }
            }
            return matrixLCS;
        }

    static HashSet<string> FindAllLcs(string X, string Y, int lenX, int lenY)
        {
            var set = new HashSet<string>();
            if (lenX == 0 || lenY == 0)
                return emptySet;
            if (X[lenX - 1] == Y[lenY - 1])
            {
                var tempResult = FindAllLcs(X, Y, lenX - 1, lenY - 1);
                foreach (var temp in tempResult)
                    set.Add(temp + X[lenX - 1]);
                return set;
            }
            if (matrixLCS[lenX - 1][lenY] >= matrixLCS[lenX][lenY - 1])
                set = FindAllLcs(X, Y, lenX - 1, lenY);
            if (matrixLCS[lenX][lenY - 1] >= matrixLCS[lenX - 1][lenY])
                set.UnionWith(FindAllLcs(X, Y, lenX, lenY - 1));
            return set;
        }

以及具有两种类型的输入和预期输出的示例:

    public void SingleOutput()
    {
    var sequence = LCS.FindLCS("ABC", "AB");
    Assert.AreEqual(1, sequence.Length);
    Assert.AreEqual("AB", sequence[0]);
    }

    public void MultipleOutput() 
    { 
    var sequence = LCS.FindLCS("BCAB", "ABC"); 
    Assert.AreEqual(2, sequence.Length); 
    Assert.AreEqual("AB", sequence [0]);
    Assert.AreEqual("BC", sequence [1]);
    }

如有任何帮助，我们将不胜感激。

Answer 1

我认为可以稍微不同地考虑动态规划。也许它可以工作:

#include <bits/stdc++.h>

using namespace std;


struct TLSTValue {
    int len;
    int cnt;
};


void update(TLSTValue& v, const TLSTValue& u) {
    if (u.cnt == 0) {
        return;
    }
    if (u.len > v.len) {
        v.len = u.len;
        v.cnt = u.cnt;
    } else if (u.len == v.len) {
        v.cnt += u.cnt;
    }
}

int main(int /* argc */, char** /* argv */)
{
    string a, b;
    while (cin >> a >> b) {
        int n = a.size();
        int m = b.size();

        vector<vector<int>> nxt(n, vector<int>(m));
        for (int j = 0; j < m; ++j) {
            int lst = n;
            for (int i = n - 1; i >= 0; --i) {
                if (a[i] == b[j]) {
                    lst = i;
                }
                nxt[i][j] = lst;
            }
        }

        vector<vector<TLSTValue>> f(n + 1, vector<TLSTValue>(m + 1, {0, 0}));
        f[0][0]= {0, 1};
        TLSTValue ans = {0, 0};
        for (int i = 0; i <= n; ++i) {
            unordered_set<char> st;
            for (int j = 0; j <= m; ++j) {
                update(ans, f[i][j]);
                if (j) {
                    update(f[i][j], f[i][j - 1]);
                }
                if (st.count(b[j])) {
                    continue;
                }
                st.insert(b[j]);
                if (i < n && j < m && f[i][j].cnt && nxt[i][j] < n) {
                    update(f[nxt[i][j] + 1][j + 1], {f[i][j].len + 1, f[i][j].cnt});
                }
            }
        }
        cout << a << " and " << b << ": length = " << ans.len << ", count = " << ans.cnt << endl;
    }

    cerr << "Time execute: " << clock() / (double)CLOCKS_PER_SEC << " sec" << endl;
    return 0;
}

nxt[i][j]是第一个开始的位置 i在字符串中的位置 a位置为 j 的字符在字符串中 b . f[i][j]是长度和计数 LCS，以字符 i - 1 结尾在字符串中 a在位置 j 之前在字符串中 b .

您可以试试代码 here .

一些测试的输出:

ABC and AB: length = 2, count = 1
BCAB and ABC: length = 2, count = 2
A and AAA: length = 1, count = 1
AAA and A: length = 1, count = 1
AAAB and ABBB: length = 2, count = 1
ABBB and AAAB: length = 2, count = 1