Longest Common Substring和Longest Common Subsequence是有区别的
X = <a, b, c, f, b, c>
Y = <a, b, f, c, a, b>
X和Y的Longest Common Sequence为<a, b, c, b>,长度为4
X和Y的Longest Common Substring为 <a, b>长度为2
其实Substring问题是Subsequence问题的特殊情况,也是要找两个递增的下标序列
<i1, i2, ...ik> 和 <j1, j2, ..., jk>使
xi1 == yj1
xi2 == yj2
......
xik == yjk
与Subsequence问题不同的是,Substring问题不光要求下标序列是递增的,还要求每次
递增的增量为1, 即两个下标序列为:
<i, i+1, i+2, ..., i+k-1> 和 <j, j+1, j+2, ..., j+k-1>
类比Subquence问题的动态规划解法,Substring也可以用动态规划解决,令
c[i][j]表示以X[i]和Y[i]结尾的公共子串的长度,如果X[i]不等于Y[i],则c[i][j]等于0, 比如
X = <y, e, d, f>
Y = <y, e, k, f>
c[1][1] = 1
c[2][2] = 2
c[3][3] = 0
c[4][4] = 1
动态转移方程为:
如果xi == yj, 则 c[i][j] = c[i-1][j-1]+1
如果xi ! = yj, 那么c[i][j] = 0
最后求Longest Common Substring的长度等于
max{c[i][j], 1<=i<=n, 1<=j<=m}
#include <stdio.h>
#include <string.h>
//#define DEBUG
#ifdef DEBUG
#define debug(...) printf( __VA_ARGS__)
#else
#define debug(...)
#endif
#define N 250
int c[N][N];
void print_str(char *s1, char *s2, int i, int j)
{
if (s1[i] == s2[j]) {
print_str(s1, s2, i-1, j-1);
putchar(s1[i]);
}
}
int common_str(char *s1, char *s2)
{
int i, j, n, m, max_c;
int x, y;
n = strlen(s1);
m = strlen(s2);
max_c = -1;
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++) {
if (s1[i-1] == s2[j-1]) {
c[i][j] = c[i-1][j-1] + 1;
}
else {
c[i][j] = 0;
}
if (c[i][j] > max_c) {
max_c = c[i][j];
x = i;
y = j;
}
debug("c[%d][%d] = %d\n", i, j, c[i][j]);
}
}
print_str(s1, s2, x-1, y-1);
printf("\n");
return max_c;
}
int main()
{
char s1[N], s2[N];
while (scanf("%s%s", s1, s2) != EOF) {
debug("%s %s\n", s1, s2);
printf("%d\n", common_str(s1, s2));
}
return 0;
}
分享到:
相关推荐
最长公共子字符串共有两种解决方法,下面具体说说我的思路方法一:Longest Common Substring和Longest Common Subsequence是有区别的X = <a>Y = <a>X和Y的Longest Common Sequence为,长度为4X和Y的Longest Common ...
最长公共子字符串(LCS)服务器概述构建一个简单的Web应用程序,允许用户在给定字符串列表的情况下请求最长公共子字符串。 功能要求通过HTTP POST解决最长的公共子字符串问题用户应该能够通过向服务器位于...
Java中的动态规划法被广泛应用于解决复杂的问题,如求解最长公共子序列(Longest Common Subsequence, LCS)和最长公共子字符串(Longest Common Substring, LSS)。这两个概念在计算机科学中尤其是在字符串处理和...
4. 额外的测试部分:定义了一个`expect`函数来检验`longestCommonSubstring`函数的输出是否符合预期。通过传入实际的计算结果和期望的值,用toBe方法进行比较,并打印出比较结果,方便调试。 在给出的测试用例中,...
在编程领域,寻找两个字符串之间的最长公共子字符串(Longest Common Substring,LCS)是一个经典的问题,它在文本处理、生物信息学以及许多其他应用中都有重要用途。本问题要求我们编写一个程序来解决这个问题,...
5. **动态规划与字符串**:例如Longest Common Subsequence(LCS)最长公共子序列,Longest Palindromic Substring(LPS)最长回文子串,这些问题是动态规划在字符串处理中的经典应用。 6. **字符串排序与压缩**:...
通过将POST请求发送到位于http:/// lcs的服务器,用户应该能够请求一组字符串中最长的公共子字符串(LCS)。 POST请求的主体必须是JSON对象,该对象代表以下格式的一组字符串: { "setOfStrings": [ {"value": ...
在计算机科学领域,尤其是在数据处理与算法设计方面,“最长公共子串”(Longest Common Substring, LCS)是一个非常重要的概念。该问题主要涉及到两个或多个字符串之间共同拥有的最长连续字符序列的寻找。这种应用...
最长公共子串(Longest Common Substring,LCS)是一个在计算机科学中常见的字符串处理问题,它涉及到查找两个或多个字符串中的最长连续子序列,这个子序列同时存在于所有字符串中。MFC,全称为Microsoft Foundation...
【Python求两个字符串最长公共子序列】 在编程领域,字符串操作是常见任务之一,而寻找两个字符串的最长公共子序列(LCS)是其中的一个经典问题。LCS是指两个字符串中都出现过的最长的连续子序列,但不考虑字符在...
在编程领域,最长公共子串(Longest Common Substring,LCS)问题是一个经典的问题,它寻找两个或多个字符串中的最长连续子序列,这个子序列同时存在于所有字符串中。在这个问题中,我们专注于PHP如何解决两个字符串...
本文将详细介绍如何利用C语言实现最大公共子串(Longest Common Substring,简称 LCS)的计算方法。最大公共子串问题是指在两个或多个字符串中找到最长的相同子串。本算法采用动态规划的方式解决这一问题,并通过一...
在文章的评论部分提到了最大公共子序列(Longest Common Subsequence, LCS)和最长公共子串(Longest Common Substring, LD)算法。这两种算法在处理字符串相似度和公共部分问题时非常有效。尤其是LCS算法,它不考虑...
最长公共子串(The Longest Common Substring) LCS问题就是求两个字符串最长公共子串的问题。解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长的1...
最长公共子串(LongestCommonSubstring)是一个非常经典的面试题目,在实际的程序中也有很高的实用价值,所以把该问题的解法总结在本文重。不过不单单只是写出该问题的基本解决代码而已,关键还是享受把学习算法一步步...
**最长公共子串(Longest Common Substring, LCS)**是两个或多个字符串中的最长字符串,该字符串同时也是这些字符串的子串。这里需要注意区分子串与子序列的概念。子串必须在原字符串中连续出现,而子序列则不必...
若不相同,则选择三个可能的子问题中LCS长度的最大值,即删除两个字符串的首字符之一,或同时删除。 以下是一个简单的递归实现LCS的算法: ```cpp void RecursionLCS(const std::string& str1, const std::string&...
此外,还有一个相似的问题是最长公共子串(Longest Common Substring,简称LCSs),与LCS的区别在于子串必须是连续的。在示例代码中,同样是通过动态规划求解,但当发现子串时,记录最大长度`rst`并清零当前位置的`...