nyoj-36 最长公共子序列(动态规划 或 递归)

最长公共子序列

描述

咱们就不拐弯抹角了，如题，需要你做的就是写一个程序，得出最长公共子序列。
tip：最长公共子序列也称作最长公共子串(不要求连续)，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。

输入

第一行给出一个整数N(0 接下来每组数据两行，分别为待测的两组字符串。每个字符串长度不大于1000.

输出

每组测试数据输出一个整数，表示最长公共子序列长度。每组结果占一行。

样例输入

2
asdf
adfsd
123abc
abc123abc

样例输出

3
6

来源

经典

上传者

hzyqazasdf
思路： 动态规划问题，由基本思想可知，问题的最优解是由子问题的最优解构成的，所以lcs(i,j) 的值与lcs(i-1, j-1), lcs(i-1, j), lcs(i, j-1) 有一定的关系。 例如： x[7] = "123abc" y[7] = "abc123abc" 首先将 问题划分，利用双层for循环： 第一层for循环如同先缩短x的长度，求x[0...i]与y的最长公共字串长度len1，然后i+1，再求x[0...i+1]与y的最长公共子串长度len2，此时，显然len2最小=len1，最大等于len1+1； 而第二层for循环相当于缩短y的长度，求x[0..i]与y[0..j]的最长公共子串leny1, 然后j +1，与上同理。最终lcs[lenx][leny]的值即为x,y最长子串的长度！ for(i = 1; i <= xs; ++i){
for(j = 1;j <= ys; ++j){ …… }
}

(图中红字代表x，y从第一个元素到该元素，例如lcs[4,5]的值代表“123a”与“abc12”的最长公共子串长度)；

< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vc3Ryb25nPgo8c3Ryb25nPtKqyLe2qGxjcyhpLGoptcQmIzIwNTQwO6Os0OjSqsrXz8ixyL3P0rvPwnhbaV0sIHlbal0gtcQmIzIwNTQwO6O6PGJyPgo8L3N0cm9uZz4KPHN0cm9uZz4gICAgICAgPC9zdHJvbmc+IDGjqSC1sXhbaV0gPT0geVtqXcqxo6zLtcP3eFtpXdPreVtqXSDSu7ao1NrX7rOkuau5stfT0PLB0NbQo6y2+GxjcyAoaSAsIGopILXEJiMyMDU0MDvOqmxjcyhpLTEsai0xKbXEJiMyMDU0MDsgJiM0MzsgMaOo0vLOqtfus6S5q7my19O0rrK70qrH88Gs0PijqaO7PGJyPgogICAgICAgMqOpILWxeFtpXSAhPSB5W2pdyrEgo6xsY3MoaSwgaim1xCYjMjA1NDA7PW1heChsY3MoaSAtIDEsIHkpLCBsY3MoaSwgeSAtIDEpKaO7CtPJ0tTJz73iys2jrLTLzOLSsr/J08O13bnpy+O3qL3ivvajrLK7uf3M4b27s6zKsaOs0ruyori9yc+0+sLrPGJyPgo8c3Ryb25nPiA8L3N0cm9uZz4KPHN0cm9uZz48YnI+Cjwvc3Ryb25nPgo8c3Ryb25nPravzKy55ruutPrC66O6PC9zdHJvbmc+CjxzdHJvbmc+PGJyPgo8L3N0cm9uZz4KPHN0cm9uZz48L3N0cm9uZz48cHJlIGNsYXNzPQ=="brush:java;">#include #include #define N 1001 int lcs[N][N]; int max(int a, int b){ return a > b a : b; } int main() { int n, i, j; char x[N], y[N]; scanf("%d", &n); while(n --){ scanf(" %s %s", x, y); int lenx = strlen(x); int leny = strlen(y); for(i = 0; i <= lenx; i ++) lcs[i][0] = 0; for(i = 1; i <= leny; i ++) lcs[0][i] = 0; for(i = 1; i <= lenx; i ++){ for(j = 1;j <= leny; j ++){ lcs[i][j] = (x[i - 1] == y[j - 1]) (lcs[i - 1][j - 1] + 1) : max(lcs[i - 1][j], lcs[i][j - 1]); } } /*for(i = 0; i <= lenx; i ++){ for(j = 0; j <= leny; j ++){ printf("%d ", lcs[i][j]); } printf("\n"); }*/ printf ("%d\n", lcs[lenx][leny]); } return 0; }
递归代码：

#include 
         
          
#include 
          
            #define N 1001 char x[N], y[N]; int max(int a, int b){ return a > b   a : b; } int f(int lenx, int leny) { if(lenx == 0 || leny == 0) return 0; if(x[lenx - 1] == y [leny - 1]) return 1 + f(lenx - 1, leny - 1); else return max(f(lenx - 1, leny), f(lenx, leny - 1)); } int main() { int n, lenx, leny, ans; scanf("%d", &n); while(n --){ scanf(" %s %s", x, y); lenx = strlen(x); leny = strlen(y); ans = f(lenx, leny); printf("%d\n", ans); } return 0; }
          
         

<script type="text/java script">

<script type="text/java script">BAIDU_CLB_fillSlot("771048");

点击复制链接 与好友分享! 回本站首页

<script> function copyToClipBoard(){ var clipBoardContent=document.title + '\r\n' + document.location; clipBoardContent+='\r\n'; window.clipboardData.setData("Text",clipBoardContent); alert("恭喜您！复制成功"); }

分享到： 更多

<script type="text/java script" id="bdshare_js" data="type=tools&uid=12732"> <script type="text/java script" id="bdshell_js"> <script type="text/java script"> var bds_config = {'snsKey':{'tsina':'2386826374','tqq':'5e544a8fdea646c5a5f3967871346eb8'}}; document.getElementById("bdshell_js").src = "http://bdimg.share.baidu.com/static/js/shell_v2.js cdnversion=" + Math.ceil(new Date()/3600000)

您对本文章有什么意见或着疑问吗？请到 论坛讨论您的关注和建议是我们前行的参考和动力