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>
-
-
-
- #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;
- }
分享到:
相关推荐
LCS(longest common substring)算法,即最大公共子串,它是求两个字符串最长公共子串的问题。大体解法是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长...
最长公共子字符串(LCS)服务器概述构建一个简单的Web应用程序,允许用户在给定字符串列表的情况下请求最长公共子字符串。 功能要求通过HTTP POST解决最长的公共子字符串问题用户应该能够通过向服务器位于...
输入两个字符串, 求它们最长公共字串的长度
最长公共子字符串共有两种解决方法,下面具体说说我的思路方法一:Longest Common Substring和Longest Common Subsequence是有区别的X = <a>Y = <a>X和Y的Longest Common Sequence为,长度为4X和Y的Longest Common ...
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Java AC 版本
C#,最大公共子序列(LCS,Longest Common Subsequences)的算法与源代码 最长的常见子序列问题是寻找两个给定字符串中存在的最长序列。 最大公共子序列算法,常用于犯罪鉴定、亲子鉴定等等的 DNA 比对。 1.1 子...
最长公共子序列Longest Common Subsequence - Super Jiju的小窝_ To be with my Dearest Jessie
题目:如果字符串一的所有字符按其在字符串...分析:求最长公共子序列(Longest Common Subsequence, LCS)是一道非常经典的动态规划题,因此一些重视算法的公司像MicroStrategy都把它当作面试题。 完整介绍动态规划将
前端工程师面试
这是动态规划中,求最长公共子序列(Longest common string)的源代码。自己编写执行。程序简单,有注释。
Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with...
通过将POST请求发送到位于http:/// lcs的服务器,用户应该能够请求一组字符串中最长的公共子字符串(LCS)。 POST请求的主体必须是JSON对象,该对象代表以下格式的一组字符串: { "setOfStrings": [ {"value": ...
C#,最长公共扩展(LCE,Longest Common Extention)的算法与源代码 考虑一个字符串s,并为每对(L,R)计算从L和R开始的s的最长子字符串。 在LCE中,在每个查询中,我们必须回答从索引L和R开始的最长公共前缀的长度...
给定两个序列X={X1, X2,···,Xm}和Y={Y1, Y2,···,Yn},找出X和Y的最长公共子序列(Longest Common Sequence)。 比如字符串X:{BDCABA};字符串Y:{ABCBDAB},则这两个字符串的最长公共子序列长度为4,最长公共...
问题描述 ...给定两个字符串,求解这两个字符串的最长公共子序列(Longest Common Sequence)。比如字符串1:BDCABA;字符串2:ABCBDAB 则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA
关于Longest Common Subsequences演算法
Longest Common Ancestor classic ppt...
给定两个字符串,求解这两个字符串的最长公共子序列(Longest Common Sequence)。比如字符串1:BDCABA;字符串2:ABCBDAB。则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA 二、算法求解 这是一个...
最大公共字符串leetcode 最长回文子串 给定一个字符串 s,找出 s 中最长的回文子串。 您可以假设 s 的最大长度为 1000。 示例 1: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. 示例 2: ...
最大公共字符串leetcode 最长回文子串 给定一个字符串 s,找出 s 中最长的回文子串。 您可以假设 s 的最大长度为 1000。 Example 1: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. Example 2: ...