Advertisement
ambition-xx

LCS

Nov 14th, 2020
209
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.82 KB | None | 0 0
  1. #include<iostream>
  2. #include<cstring>
  3. const int MAXN = 100;
  4. using namespace std;
  5. char x[MAXN] = "abcbdab";
  6. char y[MAXN] = "bdcaba";
  7. int dp[MAXN][MAXN] = {0}; //dp[i,j]:Xi与Yj的LCS的长度
  8. int b[MAXN][MAXN] = {0}; //标记函数 -1:向左 1:斜向上 0:向上
  9. int main(){
  10.     int m = strlen(x), n = strlen(y);
  11.     //初始化边界值
  12.     for(int i = 0; i < m; i++)
  13.         if(x[i]==y[0]) dp[i][0] = 1;
  14.     for(int j = 0; j < n; j++)
  15.         if(x[0]==y[j]) dp[0][j] = 1;
  16.     //迭代求解
  17.     for(int i = 1; i < m; i++){
  18.         for(int j = 1; j < n; j++){
  19.             if(x[i]==y[j]) {
  20.                 dp[i][j] = dp[i-1][j-1] + 1;
  21.                 b[i][j] = 1;
  22.             }
  23.             else if( dp[i-1][j] <= dp[i][j-1] ){
  24.                 dp[i][j] = dp[i][j-1];
  25.                 b[i][j] = -1;
  26.             } else dp[i][j] = dp[i-1][j];
  27.         }
  28.     } //时间复杂度O(mn) 空间复杂度O(mn)
  29.     cout<<dp[m-1][n-1]<<endl;
  30.     return 0;
  31. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement