Advertisement
Niktiaksk

Untitled

Nov 27th, 2022
670
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.00 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.  
  48.     vector<int> firstSubSequenceAns, secondSubSequenceAns;
  49.     while (i > 0 && j  > 0){
  50.         if (firstSubSequence[i] == secondSubSequence[j]){
  51.             firstSubSequenceAns.push_back(i - 1);
  52.             secondSubSequenceAns.push_back(j - 1);
  53.             i -= 1;
  54.             j -= 1;
  55.         } else if (dp[i][j - 1] == dp[i][j]) {
  56.             j -= 1;
  57.         } else {
  58.             i-=1;
  59.         }
  60.     }
  61.    
  62.     int sizeOfLCS = dp[lengthOfSubsequence][lengthOfSubsequence];
  63.     cout << sizeOfLCS << endl;
  64.    
  65.    
  66.     for (int i = sizeOfLCS - 1 ; i >= 0; i--) {
  67.         cout <<  firstSubSequenceAns[i]<< " ";
  68.     }
  69.     cout << endl;
  70.     for (int i = sizeOfLCS - 1 ; i >= 0; i--) {
  71.         cout << secondSubSequenceAns[i] << " ";
  72.     }
  73.     cout << endl;
  74.    
  75.     return 0;
  76. }
  77.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement