问题
如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串。
注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。
请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。
例如:输入两个字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它们的最长公共子串,
则输出它们的长度4,并打印任意一个子串。
思想
求最长公共子串(Longest
Common Subsequence, LCS)是一道非常经典的动态规划题。
在开始想这道题之前应先理解什么是LCS(最长公共子串)。如串“abcbbc”,"abccbb",其中的一个字串"abc"是其公共子串,但不时最长公共字串。最长公共子串的定义中,并不要求最长公共子串必须连续出现在两个字符串中,只需要能保持顺序的出现在序列中即可。
在理解了什么是LCS之后,LCS的递归解就容易理解了:
c[i,j] =
0
(当 i=0或者j=0)
c[i-1,j-1] +1 (xi = yj,且 i>0,j>0)
Max(c[i,j-1], c[i-1,j]
) (xi!=yj , 且i, j >0 )
c[i,j]表示字符串 X[
1, i]和Y[1, j]的LCS长度。
算法导论给出了该算法。算法分成了两步。第一步找到LCS的长度。在找LCS长度的过程中,构造运算矩阵,以方便第二步求解LCS串。
扩展
LCS的定义不要求公共子串中的字符连续出现在两个字符串中。如果要求这样做。那么该怎么来做呢。
可以想到和LCS算法差不多的算法。即也维护一个M*N的矩阵c。如果a[i]==b[j],那么c[i][j]=c[i-1][j-1]+1;当i或者j等于0时,c[i][j]=1;如果不等c[i][j]=0。
代码实现参考代码2。
代码
package com.jy.string;
public class LCS {
public static void main(String[] args) {
char[] string = "abcbbc".toCharArray();
char[] string2 = "abccbb".toCharArray();
findLCS(string, string2);
}
/**
*
* @param string
* @param string2
*/
public static void findLCS(char[] string ,char[] string2) {
int m = string.length;
int n = string2.length;
int[][] c = new int[m+1][n+1];
int[][] b = new int[m+1][n+1];
for(int i=0;i<m;i++) {
for(int j=0;j<n;j++) {
if(string[i]==string2[j]) {
c[i+1][j+1]=c[i][j]+1;
b[i+1][j+1]= '\\';
} else {
if(c[i][j+1] >= c[i+1][j]) {
c[i+1][j+1] = c[i][j+1];
b[i+1][j+1]= '|';
} else {
c[i+1][j+1] = c[i+1][j];
b[i+1][j+1]= '-';
}
}
}
}
System.out.println("LCS长度:"+c[m][n]);
System.out.println("LCS序列:");
printLCS(b,string,m,n);
}
private static void printLCS(int[][] b, char[] string, int i, int j) {
if(i==0 || j==0) {
return ;
}
if(b[i][j]=='\\') {
printLCS(b, string, i-1, j-1);
System.out.println(string[i-1]);
} else if(b[i][j]=='|'){
printLCS(b, string, i-1, j);
} else {
printLCS(b, string, i, j-1);
}
}
}
package com.jy.string;
public class LCS2 {
public static void main(String[] args) {
findLCS("abcdefg".toCharArray(), "abcdged".toCharArray());
}
public static void findLCS(char[] string1, char[] string2) {
int m = string1.length;
int n = string2.length;
int[][] c = new int[m][n];
int max=0;
int maxPosX = 0;
for(int i=0;i<m;i++) {
for(int j=0;j<n;j++) {
if(string1[i]==string2[j]) {
if(i==0||j==0) {
c[i][j] = 1;
} else {
c[i][j] = c[i-1][j-1]+1;
}
if(c[i][j]>max) {
max =c[i][j];
maxPosX = i;
}
} else {
c[i][j] = 0;
}
}
}
System.out.println(max);
for(int i = maxPosX-max+1;i<=maxPosX;i++) {
System.out.print(string1[i]);
}
}
}
分享到:
相关推荐
LCS(longest common substring)算法,即最大公共子串,它是求两个字符串最长公共子串的问题。大体解法是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长...
最长公共子序列Longest Common Subsequence - Super Jiju的小窝_ To be with my Dearest Jessie
题目:如果字符串一的所有字符... 分析:求最长公共子串(Longest Common Subsequence, LCS)是一道非常经典的动态规划题,因此一些重视算法的公司像MicroStrategy都把它当作面试题。完整介绍动态规划将需要很长的篇幅
最长公共子序列(Longest Common Subsequence, LCS),顾名思义,是指在所有的子序列中最长的那一个。子串是要求更严格的一种子序列,要求在母串中连续地出现。在上述例子的中,最长公共子序列为blog(cnblogs, ...
最长公共子串(The Longest Common Substring) LCS问题就是求两个字符串最长公共子串的问题。解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长的1...
LCS Longest (maximum) common subsequence
本文实例讲述了Python最长公共子串算法。分享给大家供大家参考。具体如下: #!/usr/bin/env python # find an LCS (Longest Common Subsequence). # *public domain* def find_lcs_len(s1, s2): m = [ [ 0 for x ...
北大POJ2533-Longest Ordered Subsequence【O(nlogn)】
最长公用子串LCS服务器 最长公共子字符串(LCS)服务器概述构建一个简单的Web应用程序,允许用户在给定字符串列表的情况下请求最长公共子字符串。 功能要求通过HTTP POST解决最长的公共子字符串问题用户应该能够通过...
最长公共子串(LongestCommonSubstring)是一个非常经典的面试题目,在实际的程序中也有很高的实用价值,所以把该问题的解法总结在本文重。不过不单单只是写出该问题的基本解决代码而已,关键还是享受把学习算法一步步...
输入两个字符串, 求它们最长公共字串的长度
Pku acm 第2533题 Longest Ordered Subsequence 代码,有详细的注释,动态规划
Longest Ordered Subsequence,算法分析与设计,C语言程序
题目:如果字符串一的所有字符按其在字符串...分析:求最长公共子序列(Longest Common Subsequence, LCS)是一道非常经典的动态规划题,因此一些重视算法的公司像MicroStrategy都把它当作面试题。 完整介绍动态规划将
北大POJ2533-Longest Ordered Subsequence 解题报告+AC代码
最长公共子序列(Longest Common Subsequence LCS)是从给定的两个序列X和Y中取出尽可能多的一部分字符,按照它们在原序列排列的先后次序排列得到。
Given two sequences X, Y and a constrained sequence P, a sequence Z is a constrained longest common subsequence for X and Y with respect to P if Z is the longest subsequence of X and Y such that P is...
最长公共子字符串共有两种解决方法,下面具体说说我的思路方法一:Longest Common Substring和Longest Common Subsequence是有区别的X = <a>Y = <a>X和Y的Longest Common Sequence为,长度为4X和Y的Longest Common ...
Estimating the Longest Increasing Subsequence in Nearly Optimal Time_在近似最优时间内估计最长增长子序列.pdf