Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- int main() {
- int lengthOfSubsequence = 0;
- cin >> lengthOfSubsequence;
- int temp;
- vector<int> firstSubSequence, secondSubSequence;
- firstSubSequence.push_back(0);
- secondSubSequence.push_back(0);
- for (int i = 0; i < lengthOfSubsequence; i++) {
- cin >> temp;
- firstSubSequence.push_back(temp);
- }
- for (int i = 0; i < lengthOfSubsequence; i++) {
- cin >> temp;
- secondSubSequence.push_back(temp);
- }
- int dp[lengthOfSubsequence + 1][lengthOfSubsequence + 1];
- for (int i = 0; i <= lengthOfSubsequence; i++) {
- for (int j = 0; j <= lengthOfSubsequence; j++) {
- dp[i][j] = 0;
- }
- }
- for (int i = 1; i <= lengthOfSubsequence; i++) {
- for (int j = 1; j <= lengthOfSubsequence; j++) {
- if (firstSubSequence[i] == secondSubSequence[j]) {
- dp[i][j] = dp[i - 1][j - 1] + 1;
- } else {
- dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
- }
- }
- }
- int i = lengthOfSubsequence, j = lengthOfSubsequence;
- vector<int> firstSubSequenceAns, secondSubSequenceAns;
- while (i > 0 && j > 0){
- if (firstSubSequence[i] == secondSubSequence[j]){
- firstSubSequenceAns.push_back(i - 1);
- secondSubSequenceAns.push_back(j - 1);
- i -= 1;
- j -= 1;
- } else if (dp[i][j - 1] == dp[i][j]) {
- j -= 1;
- } else {
- i-=1;
- }
- }
- int sizeOfLCS = dp[lengthOfSubsequence][lengthOfSubsequence];
- cout << sizeOfLCS << endl;
- for (int i = sizeOfLCS - 1 ; i >= 0; i--) {
- cout << firstSubSequenceAns[i]<< " ";
- }
- cout << endl;
- for (int i = sizeOfLCS - 1 ; i >= 0; i--) {
- cout << secondSubSequenceAns[i] << " ";
- }
- cout << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement