c# - 我怎样才能找到两个大字符串之间的 lcs 长度

Question

我在 C# 中编写了以下代码，用于获取 use 给定的两个文本的最长公共(public)子序列的长度，但它不适用于大字符串。请你帮助我好吗。我真的很困惑。

public Form1()
{
    InitializeComponent();
}

public int lcs(char[] s1, char[] s2, int s1size, int s2size)
{
    if (s1size == 0 || s2size == 0)
    {
        return 0;
    }
    else
    {
        if (s1[s1size - 1] == s2[s2size - 1])
        {
            return (lcs(s1, s2, s1size - 1, s2size - 1) + 1);
        }
        else
        {
            int x = lcs(s1, s2, s1size, s2size - 1);
            int y = lcs(s1, s2, s1size - 1, s2size);
            if (x > y)
            {
                return x;
            }
            else
                return y;
        }
    }
}

private void button1_Click(object sender, EventArgs e)
{
    string st1 = textBox2.Text.Trim(' ');
    string st2 = textBox3.Text.Trim(' ');

    char[] a = st1.ToCharArray();
    char[] b = st2.ToCharArray();

    int s1 = a.Length;
    int s2 = b.Length;

    textBox1.Text = lcs(a, b, s1, s2).ToString(); 
}

Answer 1

此处您使用的是递归方法。所以它导致程序出现你提到的性能问题。

使用动态规划 方法代替递归。

这是 C# 代码。

public static void LCS(char[] str1, char[] str2)
    {
        int[,] l = new int[str1.Length, str2.Length];
        int lcs = -1;
        string substr = string.Empty;
        int end = -1;

        for (int i = 0; i < str1.Length; i++)
        {
            for (int j = 0; j < str2.Length; j++)
            {
                if (str1[i] == str2[j])
                {
                    if (i == 0 || j == 0)
                    {
                        l[i, j] = 1;
                    }
                    else
                        l[i, j] = l[i - 1, j - 1] + 1;
                    if (l[i, j] > lcs)
                    {
                        lcs = l[i, j];
                        end = i;
                    }

                }
                else
                    l[i, j] = 0;
            }
        }

        for (int i = end - lcs + 1; i <= end; i++)
        {
            substr += str1[i];
        }

        Console.WriteLine("Longest Common SubString Length = {0}, Longest Common Substring = {1}", lcs, substr);
    }