经典算法研究by_July

》关于动态规划的算法，研究了一下现把经验教训道之一二。

具体关于动态规划为何物的介绍就不再啰嗦了，具体请看如上链接中的介绍，单对算法实现层次参数的理解给予明确。

题目如下：

题目：如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，则字符串一称之为字符串二的子串。注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出最长公共子串。例如：输入两个字符串BDCABA和ABCBDAB，字符串 BCBA和 BDAB都是是它们的最长公共子串，则输出它们的长度 4，并打印任意一个子串。

文章《

经典算法研究by_July

》中所涉及的java代码中命名为opt的二维矩阵可能让很多人郁闷。很多人会误以为他是类似lcsN的存储矩阵。即opt[i][j]存储了A[0]到A[i-1]字符串与B[0]到B[j-1]字符串的最大公共序列的长度。如果这样理解，则会非常郁闷的发现其列出的代码与动态规划的规则完全相反。笔者也在此纠结了很久。后来发现opt并非此种含义。

解释的过程中我不再用原文列出的java代码，而是用我转写的c#代码进行解释。

我们发现在打印字符串时用到的代码为：

            i = j = 0;
            while (i < m && j < n)
            {
                if (A[i] == B[j])
                {
                    System.Console.Write(A[i]);
                    i++;
                    j++;
                }
                else if (lcsN[i + 1, j] >= lcsN[i, j + 1])
                    i++;
                else
                    j++;
            }

我们将这种过程还原，假设A为：ancdf，B为：abdnghcf，当进入该循环体时首先打印a，之后应A与B都消去首字符a再做比较故运行i++；j++。之后再进行比较的是A与B分别的第二个字符n与b，发现不等，这时应比较字符串ncdf与字符串dnghcf的lcsN大还是cdf与bdnghcf的lcsN大，所以其实lcsN[i,j]意为的是字符串A[i-1]到A[m-1]与B[j-1]到B[n-1]的字符串的lcsN，所以一目了然，该程序毫无问题。全部C#版的动态规划源码如下：

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Diagnostics; namespace Dptest { class Program { static void Main(string[] args) { char[] A; char[] B; int[,] lcsN; int m, n, i, j; Stopwatch sw = new Stopwatch(); System.Console.WriteLine("Input the A:"); ; A = System.Console.ReadLine().ToCharArray(); m = A.Length; System.Console.WriteLine("Input the B:"); B = System.Console.ReadLine().ToCharArray(); n = B.Length; lcsN =new int [m + 1, n + 1]; sw.Start(); for (i = m - 1; i >= 0; i--) { for (j = n - 1; j >= 0; j--) { if (A[i] == B[j]) { lcsN[i, j] = lcsN[i + 1, j + 1] + 1; } else lcsN[i, j] = Math.Max(lcsN[i + 1, j], lcsN[i, j + 1]); } } System.Console.Write("LCS: "); i = j = 0; while (i < m && j < n) { if (A[i] == B[j]) { System.Console.Write(A[i]); i++; j++; } else if (lcsN[i + 1, j] >= lcsN[i, j + 1]) i++; else j++; } sw.Stop(); System.Console.WriteLine(""); System.Console.WriteLine("Time is: " + sw.ElapsedMilliseconds.ToString()+"毫秒"); System.Console.ReadKey(); } } }
如果只是求某两个字符串的lcs的长度，也可直接用递归求得，代码如下：

public int lcsL(AB ab, int a, int b) { if (a == -1 || b == -1) return -1; if (a == 0 && b == 0) { if (ab.A[0] == ab.B[0]) { return 1; } else { return 0; } } if (ab.A[a] == ab.B[b]) { return lcsL(ab, a - 1, b - 1) + 1; } else { return Math.Max(lcsL( ab, a - 1, b), lcsL( ab, a, b - 1)); } }

其中AB类中存储有public char[] A与public char[] B，此时求A[0]....A[m-1]与B[0].....B[n-1]的lcsL调用lcsL(ab,m-1,n-1)即可。此时的lcsL为A[0]....A[a]与，B[0].....B[b]的lcs长度，与上一个变量lcsN意味不再相同，与法则规定表示一致。

留个小问题供读者思考：如果题目换为输出所有的lcs呢？该怎么改？