求两个输入的字符串的最长公共子串
算法：求两个字符串的最长公共子串
原理：
（1） 将连个字符串分别以行列组成一个矩阵。
（2）。若该矩阵的节点对应的字符相同，则该节点值为1。
（3）当前字符相同节点的值 = 左上角(d[i-1, j-1])的值 +1，这样当前节点的值就是最大公用子串的长。
(s2) b c d e
(s1)
a 0 0 0 0
b 1 0 0 0
c 0 2 0 0
d 0 0 3 0
3. 结果：只需以行号和最大值为条件即可截取最大子串
C# code:
[csharp] view plaincopyprint?
public static string MyLCS(string s1, string s2)
{
if (String.IsNullOrEmpty(s1) || String.IsNullOrEmpty(s2))
{
return null;
}
else if (s1 == s2)
{
return s1;
}
int length = 0;
int end = 0;
int[,] a = new int[s1.Length, s2.Length];
for (int i = 0; i s1.Length; i++)
{
for (int j = 0; j s2.Length; j++)
{
int n = (i – 1 = 0 j – 1 = 0) ? a[i – 1, j – 1] : 0;
a[i, j] = s1[i] == s2[j] ? 1+n : 0;
if (a[i, j] length)
{
length = a[i,j];
end = i;
}
}
}
return s1.Substring(end – length + 1, length);
}
java语言中编程求解两个字符串最长相同字符串的长度
public class StringTest4 {
/**
* @param args
*/
public static void main(String[] args) {
/*
* 需求4：两个字符串的最大相同子串。
* “sadfcctvghjkl”
* “zxcctvcv”
*
* 思路：
* 1，以短的字符串为主。
* 到长的字符串中去判断是否存在，如果存在，已找到。
* 2，如果没有找到。将短的字符串的长度递减获取子串继续到长的串中查找。只要找到就结束。
* 3，没有找到，说明没有相同的。
*
*/
String s1 = “sadfcctvghjkl”;
String s2 = “zxcctvcv”;
String maxSub = getMaxSubString(s2,s1);
System.out.println(“maxsub=”+maxSub+” length=”+maxSub.length());
}
public static String getMaxSubString(String s1, String s2) {
//确定哪个是长的哪个是短的。
String longStr,shortStr;
longStr = s1.length()s2.length()?s1:s2;
shortStr = s1.equals(longStr)?s2:s1;
//System.out.println(“long:”+longStr);
//System.out.println(“short:”+shortStr);
//对短的字符串操作，从短串中取子串，到长字符串中判断，是否存在。
for(int x=0; xshortStr.length(); x++){
for(int y=0,z=shortStr.length()-x; z=shortStr.length(); y++,z++){
//根据y，z，获取子串。
String temp = shortStr.substring(y,z);
//System.out.println(temp);
if(longStr.contains(temp))
return temp;
}
}
return null;
}
}
用JAVA编写一个程序实现，计算两个字符串最长相同子串的长度。
(int
j
=
i;
j
s1.length();
j++)
改为
(int
j
=
i;
j
s1.length()+1;
j++)
因为substring(start,
end)方法中end是不取值的，也就是结尾取end-1，你可以试试两个相同字符串比较会少找一个
2021-02-11：如何求出两个字符串的最大公共子序列长度？
具体函数因语言不同而有差异。
这里说下思路。
1、选择短的那个字符串进行循环枚举子串，这样效率高一些。假定它是 a，长度 k。另一个字符串为 b。
2、两层循环，第一层，子串的起点，循环变量 i=1 到 k-1；第二层，子串起点 i，循环变j= i+1 到 k，作为字串终点。
3、在第二层循环内，对子串i到j用函数查询它在字符串b中的位置，比如 fortran 的 index 函数，若是它的字串，将字串保留到一个副本 t 中，记录字串的长度 s。s 的初值定为0。
4、每找到一共公共子串，将长度与 s 进行比较，大于它的，替换 s，保存字串到 t。
5、完成两层循环后，输出 t 和 s。
java 两个字符串,求最长公共子串的长度
用动态规划，
if (s1[i] == s2[j])
dp[i][j] = dp[i – 1][j – 1] + 1;
else
dp[i][j] = max(dp[i – 1][j], dp[i][j – 1]);
微信扫一扫 
支付宝扫一扫 
