`
dqifa
  • 浏览: 115947 次
社区版块
存档分类
最新评论

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

分享到:
评论

相关推荐

    字符串相似性算法【最长公共字符串算法】 【LCS】

    最长公共子序列(Longest Common Subsequence, LCS)是其中一种广泛应用的方法,尤其在文本处理、生物信息学和数据比较中有着广泛的应用。这篇博客文章可能是关于如何实现LCS算法的讨论,虽然具体的博文内容没有提供...

    C语言求解最长公共子字符串问题及相关的算法分析

    题目:如果字符串一的所有字符按其在字符串...分析:求最长公共子序列(Longest Common Subsequence, LCS)是一道非常经典的动态规划题,因此一些重视算法的公司像MicroStrategy都把它当作面试题。 完整介绍动态规划将

    lcs.rar_Common Subsequence_LCS_lcs matlab_subsequence

    最长公共子序列(Longest Common Subsequence,简称LCS)是计算机科学中一种经典的问题,主要涉及字符串或序列的比较和分析。这个问题在文本编辑器的差异计算、生物信息学的DNA序列比对以及程序代码的相似性检测等多...

    求字符串的最长公共子序列

    最长公共子序列(Longest Common Subsequence,LCS)是计算机科学中一种经典的字符串问题,主要涉及算法设计和分析。它的目标是找到两个给定序列(通常为字符串)的最长子序列,该子序列在原序列中不需连续,但必须...

    字符串相似度比较算法

    LCS 是两个字符串中最长的公共子序列的长度。它不关心字符的相对位置,只关注子序列的长度。LCS 通常用于比较长文本的相似性。 6. **余弦相似度**: 通过计算两个字符串的词袋模型向量之间的夹角余弦值来衡量相似...

    从“公共子串”的角度来分析求解“最长公共子序列”(LCS)

    最长公共子序列(Longest Common Subsequence,简称LCS)是计算机科学中一个经典的问题,主要涉及字符串处理和算法设计。在这个问题中,我们需要找到两个或多个字符串的最长子序列,这个子序列并不一定是连续的,但...

    Python求两个字符串最长公共子序列代码实例

    在编程领域,字符串操作是常见任务之一,而求解两个字符串的最长公共子序列(Longest Common Subsequence, LCS)是字符串处理中的一个重要问题。这个问题涉及到动态规划算法,它能有效地解决这类具有最优子结构和...

    求两个字符串的最长公共子序列.pdf

    本文将详细介绍最长公共子序列(Longest Common Subsequence,LCS)算法的概念、原理和实现。LCS 是一种经典的字符串处理算法,广泛应用于自然语言处理、数据压缩、生物信息学等领域。 什么是最长公共子序列? ...

    利用C++实现最长公共子序列与最长公共子串

    在计算机科学中,字符串处理是常见的任务之一,其中最长公共子序列(Longest Common Subsequence, LCS)和最长公共子串(Longest Common Substring, LSCS)是两个重要的概念。子序列不强调元素在原序列中的连续性,...

    ACM-字符串处理专练

    5. **动态规划与字符串**:例如Longest Common Subsequence(LCS)最长公共子序列,Longest Palindromic Substring(LPS)最长回文子串,这些问题是动态规划在字符串处理中的经典应用。 6. **字符串排序与压缩**:...

    lcs.rar_LCS_LCS算法_Lcs.rar_最长公共子序列

    最长公共子序列(Longest Common Subsequence,简称LCS)是一种经典的计算机科学问题,主要应用于比较和分析序列,如文本、DNA序列或编程语言源代码。LCS算法旨在找到两个给定序列之间的最长子序列,这个子序列并不...

    LCS最长公共子序列算法

    **最长公共子序列(Longest Common Subsequence, LCS)算法详解** 在计算机科学中,LCS算法是一个经典的字符串处理问题,用于寻找两个序列的最长子序列,这个子序列不必是连续的,但必须保持原序列的相对顺序。该...

    使用Java实现的计算两字符串相似度+最长公共子序列.zip

    在计算机科学领域,字符串处理是常见的一类任务,其中计算两个字符串的相似度以及找到它们的最长公共子序列(Longest Common Subsequence, LCS)是一个经典的问题。本篇将深入探讨这个问题,以及如何使用Java来解决...

    Java基于动态规划法实现求最长公共子序列及最长公共子字符串示例

    Java中的动态规划法被广泛应用于解决复杂的问题,如求解最长公共子序列(Longest Common Subsequence, LCS)和最长公共子字符串(Longest Common Substring, LSS)。这两个概念在计算机科学中尤其是在字符串处理和...

    LCS.rar_LCS_lcs algorithm_最长公共子序列

    最长公共子序列(Longest Common Subsequence,简称LCS)是计算机科学中一种经典的问题,主要涉及字符串或序列的比较。在本压缩包文件"LCS.rar"中,包含了一个名为"LCS"的程序,该程序可能用C++实现了KMP算法来解决...

    LCS.rar_LCS_lcs matlab_字符 匹配_字符匹配

    标题中的"LCS.rar"指的是一个压缩包文件,其中包含了与最长公共子序列(Longest Common Subsequence, LCS)算法相关的代码。LCS是一种在计算机科学中广泛使用的算法,主要用于找出两个序列之间的最长子序列,而这...

    Delphi计算字符串的相似度

    5. **最长公共子序列(Longest Common Subsequence, LCS)**:找到两个字符串中的最长子串,它们在各自的字符串中都存在,但不一定连续。LCS的长度可以作为相似度的一个度量。 在Delphi中实现这些算法,你需要理解...

    算法题示例-最长公共子序列.rar

    算法题目:最长公共子序列(Longest Common Subsequence, LCS) 题目描述: 给定两个字符串 text1 和 text2,找到这两个字符串的最长公共子序列(LCS)的长度。一个字符串的子序列是指这样一个字符串:它通过删除原...

    LCS.rar_LCS_lcs matlab_最长公共子序列

    最长公共子序列(Longest Common Subsequence, LCS)是计算机科学中一种经典的字符串问题,它在序列比对、数据挖掘、生物信息学等领域有广泛应用。本压缩包“LCS.rar”包含了一个用C++实现的LCS算法,同时也提到了与...

Global site tag (gtag.js) - Google Analytics