Advertisement
Niktiaksk

Untitled

Nov 27th, 2022
558
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.29 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int main() {
  6.    
  7.     int lengthOfSubsequence = 0;
  8.     cin >> lengthOfSubsequence;
  9.    
  10.     int temp;
  11.     vector<int> firstSubSequence, secondSubSequence;
  12.    
  13.     firstSubSequence.push_back(0);
  14.     secondSubSequence.push_back(0);
  15.    
  16.     for (int i = 0; i < lengthOfSubsequence; i++) {
  17.         cin >> temp;
  18.         firstSubSequence.push_back(temp);
  19.     }
  20.    
  21.     for (int i = 0; i < lengthOfSubsequence; i++) {
  22.         cin >> temp;
  23.         secondSubSequence.push_back(temp);
  24.     }
  25.    
  26.    
  27.     int dp[lengthOfSubsequence + 1][lengthOfSubsequence + 1];
  28.    
  29.     for (int i = 0; i <= lengthOfSubsequence; i++) {
  30.         for (int j = 0; j <= lengthOfSubsequence; j++) {
  31.             dp[i][j] = 0;
  32.         }
  33.     }
  34.    
  35.                
  36.     for (int i = 1; i <= lengthOfSubsequence; i++) {
  37.         for (int j = 1; j <= lengthOfSubsequence; j++) {
  38.             if (firstSubSequence[i] == secondSubSequence[j]) {
  39.                 dp[i][j] = dp[i - 1][j - 1] + 1;
  40.             } else {
  41.                 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
  42.             }
  43.         }
  44.     }
  45.    
  46.     int i = lengthOfSubsequence, j = lengthOfSubsequence;
  47.     vector<int> firstSubSequenceAns, secondSubSequenceAns, myLCS;
  48.    
  49.     while (i >= 1 && j >= 1){
  50.         if (firstSubSequence[i] == secondSubSequence[j]){
  51.             firstSubSequenceAns.push_back(i - 1);
  52.             secondSubSequenceAns.push_back(j - 1);
  53.             myLCS.push_back(firstSubSequence[i]);
  54.             i -= 1;
  55.             j -= 1;
  56.         } else if (dp[i - 1][j] == dp[i][j]) {
  57.             i -= 1;
  58.         } else {
  59.             j-=1;
  60.         }
  61.     }
  62.    
  63.     int sizeOfLCS = dp[lengthOfSubsequence][lengthOfSubsequence];
  64.     cout << sizeOfLCS << endl;
  65.    
  66.  
  67. //    for(int i = 0; i < lengthOfSubsequence + 1; i++){
  68. //        for(int j = 0; j < lengthOfSubsequence + 1; j++){
  69. //            cout << dp[i][j] << " ";
  70. //        }
  71. //        cout << endl;
  72. //    }
  73. //    cout << endl;
  74.    
  75.    
  76.     for (int i = sizeOfLCS - 1 ; i >= 0; i--) {
  77.         cout <<  firstSubSequenceAns[i]<< " ";
  78.     }
  79.     cout << endl;
  80.     for (int i = sizeOfLCS - 1 ; i >= 0; i--) {
  81.         cout << secondSubSequenceAns[i] << " ";
  82.     }
  83.     cout << endl;
  84.    
  85.     return 0;
  86. }
  87.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement