当前位置:   article > 正文

Common Subsequence(最长公共子序列+动态规划)hdu1159 经典_c程序common subsequence

c程序common subsequence

Common Subsequence

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 29329    Accepted Submission(s): 13174


Problem Description
A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = <x1, x2, ..., xm> another sequence Z = <z1, z2, ..., zk> is a subsequence of X if there exists a strictly increasing sequence <i1, i2, ..., ik> of indices of X such that for all j = 1,2,...,k, xij = zj. For example, Z = <a, b, f, c> is a subsequence of X = <a, b, c, f, b, c> with index sequence <1, 2, 4, 6>. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y. 
The program input is from a text file. Each data set in the file contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct. For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line. 
 

Sample Input
  
  
abcfbc abfcab programming contest abcd mnp
 

Sample Output
  
  
4 2 0
 

Source



链接:http://acm.hdu.edu.cn/showproblem.php?pid=1159

题意:求两个字符串的最长公共子串。

思路:动态规划。

最长公共子序列是一个很经典的动态规划问题,最近正在学习动态规划,所以拿来这里再整理一下。

这个问题在《算法导论》中作为讲动态规划算法的例题出现。


动态规划,众所周知,第一步就是找子问题,也就是把一个大的问题分解成子问题。这里我们设两个字符串A、B,A = "a0, a1, a2, ..., am-1",B = "b0, b1, b2, ..., bn-1"。

(1)如果am-1 == bn-1,则当前最长公共子序列为"a0, a1, ..., am-2"与"b0, b1, ..., bn-2"的最长公共子序列与am-1的和。长度为"a0, a1, ..., am-2"与"b0, b1, ..., bn-2"的最长公共子序列的长度+1。

(2)如果am-1 != bn-1,则最长公共子序列为max("a0, a1, ..., am-2"与"b0, b1, ..., bn-1"的公共子序列,"a0, a1, ..., am-1"与"b0, b1, ..., bn-2"的公共子序列)

如果上述描述用数学公式表示,则引入一个二维数组c[][],其中c[i][j]记录X[i]与Y[j]的LCS长度,b[i][j]记录c[i][j]是通过哪一个子问题的值求得的,即,搜索方向。

这样我们可以总结出该问题的递归形式表达:

recursive formula

按照动态规划的思想,对问题的求解,其实就是对子问题自底向上的计算过程。这里,计算c[i][j]时,c[i-1][j-1]、c[i-1][j]、c[i][j-1]已经计算出来了,这样,我们可以根据X[i]与Y[j]的取值,按照上面的递推,求出c[i][j],同时把路径记录在b[i][j]中(路径只有3中方向:左上、左、上,如下图)。

flow

计算c[][]矩阵的时间复杂度是O(m*n);根据b[][]矩阵寻找最长公共子序列的过程,由于每次调用至少向上或向左移动一步,这样最多需要(m+n)次就会i = 0或j = 0,也就是算法时间复杂度为O(m+n)。


  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #include<algorithm>
  5. using namespace std;
  6. int map[10005][10005];
  7. string str1,str2;
  8. int len1,len2;
  9. //最长公共子序列
  10. /***
  11. 递归解法:
  12. 0 if(i==0||j==0);
  13. map[i][j] = map[i-1][j-1] if(i>0&&j>0&&str1[i]==str2[j])
  14. max(map[i-1][j],map[i][j-1]) if(i>0&&j>0&&str1[i]!=str2[j])
  15. */
  16. /*****递归超时了!
  17. int LCS(int x,int y)
  18. {
  19. if(x<0||y<0) return 0;
  20. if( str1[x]==str2[y]) return LCS(x-1,y-1)+1;
  21. else return max(LCS(x-1,y),LCS(x,y-1));
  22. }*/
  23. int main()
  24. {
  25. while(cin>>str1>>str2)
  26. {
  27. len1=str1.length()-1;
  28. len2=str2.length()-1;
  29. // printf("%d\n",LCS(len1,len2));
  30. /***非递归解法LCS*/
  31. for(int i=0;i<=len1+1;i++)
  32. {
  33. for(int j=0;j<=len2+1;j++)
  34. {
  35. if(i==0||j==0) {map[i][j]=0;continue;}
  36. if(str1[i-1]==str2[j-1])
  37. {
  38. map[i][j]=map[i-1][j-1]+1;
  39. }
  40. else
  41. {
  42. map[i][j]=max(map[i-1][j],map[i][j-1]);
  43. }
  44. }
  45. }
  46. printf("%d\n",map[len1+1][len2+1]);
  47. }
  48. return 0;
  49. }


还有一种优化空间的方法,利用滚动数组!这里也附上代码。在不需要记录路径的时候很好用!


  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4. #include<algorithm>
  5. using namespace std;
  6. int map[2][10005];
  7. string str1,str2;
  8. int len1,len2;
  9. //最长公共子序列
  10. int LCS(int x,int y)
  11. {
  12. for(int i=0;i<=x;i++)
  13. {
  14. for(int j=0;j<=y+1;j++)
  15. {
  16. if(i==0||j==0) {map[i%2][j]=0;continue;}
  17. if(str1[i-1]==str2[j-1])
  18. {
  19. map[i%2][j]=map[(i-1)%2][j-1]+1;
  20. }
  21. else
  22. {
  23. map[i%2][j]=max(map[(i-1)%2][j],map[i%2][j-1]);
  24. }
  25. }
  26. }
  27. }
  28. int main()
  29. {
  30. while(cin>>str1>>str2)
  31. {
  32. len1=str1.length();
  33. len2=str2.length();
  34. LCS(len1,len2);
  35. printf("%d\n",map[len1%2][len2]);
  36. }
  37. return 0;
  38. }



声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家自动化/article/detail/169526
推荐阅读
相关标签
  

闽ICP备14008679号