最长公共子序列

男娘i 2022-09-30 10:00 333阅读 0赞 
  1. #include <iostream>
  2. #include <assert.h>
  3. #include <string>
  5. using namespace std;
  7. #define Max(a,b) (a)>(b)?(a):(b)
  8. int main(void)
  9. {
  10.     string str1 = "abcdss";
  11.     string str2 = "asbda";
  13.     int len1 = str1.length();
  14.     int len2 = str2.length();
  16.     int A[50][50] = { 0 };
  18.     for (int i = 1; i <= len1; i++)
  19.     {
  20.         for (int j = 1; j <= len2; j++)
  21.         {
  22.             if (str1[i-1] == str2[j-1])
  23.             {
  24.                 A[i][j] = A[i - 1][j - 1] + 1;
  25.             }
  26.             else
  27.             {
  28.                 A[i][j] = Max(A[i - 1][j], A[i][j - 1]);
  29.             }
  30.         }
  31.     }
  33.     cout << "最长公共子序列元素个数: "<<A[len1][len2]<<endl;
  34.     cout << "最长公共序列(逆序)" << endl;
  36.     for (int i = len1-1,j = len2-1; i >= 0 && j >= 0; )
  37.     {
  38.         if (str1[i] == str2[j])
  39.         {
  40.             cout << str1[i];
  41.             i--; j--;
  42.         }
  43.         else
  44.         {
  45.             if (A[i][j+1] >= A[i+1][j])
  46.             {
  47.                 i--;
  48.             }
  49.             else
  50.             {
  51.                 j--;
  52.             }
  53.         }
  54.     }
  56.     return 0;
  57. }

参考博客： http://www.cnblogs.com/huangxincheng/archive/2012/11/11/2764625.html

发表评论

表情：
评论列表 （有 0 条评论，333人围观）

还没有评论，来说两句吧...

相关阅读

    相关 最长公共子序列

    最长公共子序列 时间限制：3000 ms | 内存限制：65535 KB 难度：3 描述 咱们就不拐弯抹角了，如题，需要你做的就是写一个程序，得出最长公共子序列

    骑猪看日落骑猪看日落/ 0 赞/ 321 阅读

    相关 最长公共子序列

    一个序列的子序列是该序列中删除某些元素后得到的序列。给定两个子序列X和Y，求二者的最长公共子序列。 例如，X=\{A,B,C,B,D,A,B\}，Y=\{B,D,C,A,B,

    超、凢脫俗超、凢脫俗/ 0 赞/ 321 阅读

    相关 最长公共子序列

    最长公共子序列 最长公共子序列与最长公共子串的区别在于最长公共子序列不要求在原字符串中是连续的，比如ADE和ABCDE的最长公共子序列是ADE。 我们用动态规划的方法来思考

    向右看齐向右看齐/ 0 赞/ 328 阅读