[BOJ] 5582 - 공통 부분 문자열 (C++)
문제
코드
#include <iostream>
using namespace std;
int dp[4001][4001];
int main(void){
string a, b;
int m = 0;
cin >> a >> b;
for (int i = 1; i <= a.size(); i++){
for (int j = 1; j <= b.size(); j++){
if (a[i-1] == b[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
m = max(m, dp[i][j]);
}
}
}
cout << m;
return 0;
}
접근
이 문제는 전형적인 LCS(Longest Common substring) 이다. 진행 과정은 다음과 같다.
1. 문자열A, 문자열B의 한글자씩 비교한다.
2. 두 문자가 다르다면 LCS[i][j]에 0을 표시한다.
3. 두 문자가 같다면 LCS[i - 1][j - 1] 값을 찾아 +1 한다.
4. 위 과정을 반복한다.
현재 두 문자가 같을때 두 문자의 앞 글자까지가 공통 문자열이라면 계속 공통 문자열이 이어질 것이고, 아니라면 본인부터 다시 공통 문자열을 만들어 가게 될 것이다. 따라서 위와 같은 순서로 진행하면 된다.
Author And Source
이 문제에 관하여([BOJ] 5582 - 공통 부분 문자열 (C++)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@keybomb/BOJ-5582-공통-부분-문자열-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)