-
Notifications
You must be signed in to change notification settings - Fork 2
/
9252.cpp
51 lines (41 loc) · 772 Bytes
/
9252.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int LCS[1001][1001];
int main(){
vector<char> result;
string str1, str2;
int i, j;
cin>>str1;
cin>>str2;
for(i=1; i<=str1.size(); i++){
for(j=1; j<=str2.size() ; j++){
if(str1[i-1] == str2[j-1]){
LCS[i][j] = LCS[i-1][j-1]+1;
}else{
if(LCS[i-1][j] < LCS[i][j-1]){
LCS[i][j] = LCS[i][j-1];
}else{
LCS[i][j] = LCS[i-1][j];
}
}
}
}
printf("%d\n", LCS[i-1][j-1]);
i = str1.size();
j = str2.size();
while(i>=1 && j>=1){
if(LCS[i][j] == LCS[i-1][j]){
i--;
}else if(LCS[i][j] == LCS[i][j-1]){
j--;
}else{
result.push_back(str1[i-1]);
i--; j--;
}
}
for(i=result.size()-1; i>=0; i--)
printf("%c", result[i]);
return 0;
}