쾌락없는 책임 (공부)/알고리즘 문제풀이
[Algorithm] 백준 5582 공통 부분 문자열 - C++, LCS, DP
허스크
2023. 6. 11. 13:43
반응형
5582번: 공통 부분 문자열
두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들
www.acmicpc.net
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int MAX = 4001;
int LCS[MAX][MAX];
string s1, s2;
int main(){
int maxLength = -1;
cin >> s1;
cin >> s2;
for(int i = 1; i <= s1.size(); i++){
for(int j = 1; j <= s2.size(); j++){
LCS[i][j] = (s1[i-1] == s2[j-1]) ? LCS[i-1][j-1] + 1 : 0;
maxLength = max(LCS[i][j], maxLength);
}
}
cout << maxLength << '\n';
}기본적인 공통 부분 문자열 문제였습니다. 알고리즘을 이해한 뒤 풀이하면 쉽게 풀이할 수 있습니다.
반응형