알고리즘
https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence
LCS 알고리즘을 굉장히 잘 설명한 글이 있어 링크로 대체
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;
string s[2];
int map[1011][1011];
int max(int a, int b) {
return a < b ? b : a;
}
int main() {
cin >> s[0] >> s[1];
for (int i = 1; i <= s[1].size(); i++) {
for (int j = 1; j <= s[0].size(); j++) {
if (s[1][i - 1] == s[0][j - 1])
map[i][j] = map[i - 1][j - 1] + 1;
else
map[i][j] = max(map[i - 1][j], map[i][j - 1]);
}
}
cout << map[s[1].size()][s[0].size() ];
}