LCS (Longest Common Subsequence) 字符串最长公共子串算法

LCS (Longest Common Subsequence) 算法用于找出两个字符串最长公共子串。

算法原理：

(1) 将两个字符串分别以行和列组成矩阵。
(2) 计算每个节点行列字符是否相同，如相同则为 1。
(3) 通过找出值为 1 的最长对角线即可得到最长公共子串。

　 人 民 共 和 时 代
中 0, 0, 0, 0, 0, 0
华 0, 0, 0, 0, 0, 0
人 1, 0, 0, 0, 0, 0
民 0, 1, 0, 0, 0, 0
共 0, 0, 1, 0, 0, 0
和 0, 0, 0, 1, 0, 0
国 0, 0, 0, 0, 0, 0

为进一步提升该算法，我们可以将字符相同节点(1)的值加上左上角(d[i-1, j-1])的值，这样即可获得最大公用子串的长度。如此一来只需以行号和最大值为条件即可截取最大子串。

　 人 民 共 和 时 代
中 0, 0, 0, 0, 0, 0
华 0, 0, 0, 0, 0, 0
人 1, 0, 0, 0, 0, 0
民 0, 2, 0, 0, 0, 0
共 0, 0, 3, 0, 0, 0
和 0, 0, 0, 4, 0, 0
国 0, 0, 0, 0, 0, 0

public static string LCS(string s1, string s2)
{
    if (s1 == s2)
        return s1;
    else if (String.IsNullOrEmpty(s1) || String.IsNullOrEmpty(s2))
        return null;

    var d = new int[s1.Length, s2.Length];

    var index = 0;
    var length = 0;

    for (int i = 0; i < s1.Length; i++)
    {
        for (int j = 0; j < s2.Length; j++)
        {
            // 左上角值
            var n = i - 1 >= 0 && j - 1 >= 0 ? d[i - 1, j - 1] : 0;

            // 当前节点值 = "1 + 左上角值" : "0"
            d[i, j] = s1[i] == s2[j] ? 1 + n : 0;

            // 如果是最大值，则记录该值和行号
            if (d[i, j] > length)
            {
                length = d[i, j];
                index = i;
            }
        }
    }

    return s1.Substring(index - length + 1, length);
}

 另外提供Java版本

LCS(Longest Common Subsequence) 就是求两个字符串最长公共子串的问题。

比如：

  String str1 = new String("adbccadebbca");
  String str2 = new String("edabccadece");
str1与str2的公共子串就是bccade.

    解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况，若是匹配则为1，否则为0。然后求出对角线最长的1序列，其对应的位置就是最长匹配子串的位置.
    下面是字符串21232523311324和字符串312123223445的匹配矩阵，前者为X方向的，后者为Y方向的。不难找到，红色部分是最长的匹配子串。通过查找位置我们得到最长的匹配子串为：21232

0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
　　 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0
　　 1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
　　 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0
　　 1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
　　 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
　　 1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
　　 1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
　　 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
　　 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
　　 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
　　 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
　　 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
                                                                                                                           
但是在0和1的矩阵中找最长的1对角线序列又要花去一定的时间。通过改进矩阵的生成方式和设置标记变量，可以省去这部分时间。下面是新的矩阵生成方式：

        0 0 0 1 0 0 0 1 1 0 0 1 0 0 0
　　 0 1 0 0 0 0 0 0 0 2 1 0 0 0 0
　　 1 0 2 0 1 0 1 0 0 0 0 0 1 0 0
　　 0 2 0 0 0 0 0 0 0 1 1 0 0 0 0
　　 1 0 3 0 1 0 1 0 0 0 0 0 1 0 0
　　 0 0 0 4 0 0 0 2 1 0 0 1 0 0 0
　　 1 0 1 0 5 0 1 0 0 0 0 0 2 0 0
　　 1 0 1 0 1 0 1 0 0 0 0 0 1 0 0
　　 0 0 0 2 0 0 0 2 1 0 0 1 0 0 0
　　 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
　　 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
　　 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
　　 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

    当字符匹配的时候，我们并不是简单的给相应元素赋上1，而是赋上其左上角元素的值加一。我们用两个标记变量来标记矩阵中值最大的元素的位置，在矩阵生成的过程中来判断当前生成的元素的值是不是最大的，据此来改变标记变量的值，那么到矩阵完成的时候，最长匹配子串的位置和长度就已经出来了。
　　这样做速度比较快，但是花的空间太多。我们注意到在改进的矩阵生成方式当中，每生成一行，前面的那一行就已经没有用了。因此我们只需使用一维数组即可。最终的代码如下：

public class LCString2 {

    public static void getLCString(char[] str1, char[] str2)
    {
        int i,j;
        int len1,len2;
        len1 = str1.length;
        len2 = str2.length;
        int maxLen = len1 > len2?len1:len2;
        int[] max = new int[maxLen];
        int[] maxIndex = new int[maxLen];
        int[] c = new int[maxLen];
        
        for (i = 0; i < len2 ; i++)
        {
            for (j = len1 -1; j >= 0; j--)
            {
                if (str2[i] == str1[j]) 
                {
                    if ( ( i == 0) || (j == 0) )
                        c[j] = 1;
                    else
                        c[j] = c[j-1] + 1;
                }
                else
                {
                    c[j] = 0;
                }
                
                if (c[j] > max[0])
                {   //如果是大于那暂时只有一个是最长的,而且要把后面的清0;
                    max[0] = c[j];
                    maxIndex[0] = j;
                    
                    for (int k = 1; k < maxLen; k++)
                    {
                        max[k] = 0;
                        maxIndex[k] = 0;
                    }
                }
                else if (c[j] == max[0])
                {   //有多个是相同长度的子串
                    for (int k = 1; k < maxLen; k++)
                    {
                        if (max[k] == 0)
                        {
                            max[k] = c[j];
                            maxIndex[k] = j;
                            break;  //在后面加一个就要退出循环了
                        }
                
                    }
                }
            }
        }
        
        for (j = 0; j < maxLen; j++)
        {
            if (max[j] > 0)
            {
                System.out.println("第" + (j + 1) + "个公共子串:");
                for (i = maxIndex[j] - max[j] + 1; i <= maxIndex[j]; i++)
                    System.out.print(str1[i]);
                System.out.println(" ");
            }            
        }
    }

    public static void main(String[] args) {
        
        String str1 = new String("adbba1234");
        String str2 = new String("adbbf1234sa");
        getLCString(str1.toCharArray(),str2.toCharArray());
    }
}

 运行结果：

C:\java>java LCString2
第1个公共子串:
adbb
第2个公共子串:
1234

from：http://cdzm.ccsu.cn/forum.php?mod=viewthread&tid=27006