mickypinata

PROG-T1019: DNA

Sep 18th, 2021
558
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 200;
  5.  
  6. string strA, strB;
  7. int dp[N + 1][N + 1];
  8.  
  9. int main(){
  10.  
  11.     cin >> strA >> strB;
  12.     int mx = 0;
  13.     int idx = 0;
  14.     for(int i = 1; i <= strA.size(); ++i){
  15.         for(int j = 1; j <= strB.size(); ++j){
  16.             if(strA[i - 1] == strB[j - 1]){
  17.                 dp[i][j] = 1 + dp[i - 1][j - 1];
  18.             }
  19.             if(dp[i][j] > mx){
  20.                 mx = dp[i][j];
  21.                 idx = i;
  22.             }
  23.         }
  24.     }
  25.     cout << strA.substr(idx - mx, mx);
  26.  
  27.     return 0;
  28. }
  29.  
RAW Paste Data