[백준 5582] 공통 부분 문자열 C++

문제

백준 5582 공통 부분 문자열 C++

5582번: 공통 부분 문자열

풀이

예제 입력을 보겠습니다.

	A	B	R	A	C	A	D	A	B	R	A
E
C					1
A	1			1		1		1			1
D							1
A	1			1		1		1			1
D							1
A	1			1		1		1			1
B		1							1
R			1							1
B		1							1
C					1
R			1							1
D							1
A	1			1		1		1			1
R			1							1
A	1			1		1		1			1

s1를 문자열 1의 길이, s2를 문자열 2의 길이라고 하면

dp[0][0] 부터 dp[s2-1][s1-1] 까지 루프를 돌면서 s1과 s2가 같은 경우 1을 넣어줍니다.

	A	B	R	A	C	A	D	A	B	R	A
E
C					1
A	1			1		2		1			1
D							3
A	1			1		1		4			1
D							2
A	1			1		1		3			1
B		2							4
R			3							5
B		1							1
C					1
R			1							1
D							1
A	1			1		1		2			1
R			1							1
A	1			2		1		1			2

1을 넣어줬다면(s1[j] == s2[i]라면), 문자열이 연속되는 상태이므로 dp[i][j]에서 dp[i-1][j-1] 만큼을 더해줍니다.

그 후 dp의 최댓값을 갱신해줍니다.

dp의 최댓값이 공통부분문자열의 최대 길이가 됩니다.

 

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
 
int main() {
    string s1, s2;
    cin >> s1 >> s2;
    int ans = 0;
    // dp[s2][s1];
    vector<vector<int>> dp(s2.length(), vector<int>(s1.length(), 0));
    for (int i = 0; i < s2.length(); i++) {
        for (int j = 0; j < s1.length(); j++) {
            if (s2[i] == s1[j]) {
                dp[i][j] = 1;
                if (i >= 1 && j >= 1) {
                    dp[i][j] += dp[i - 1][j - 1];
                }
                ans = max(ans, dp[i][j]);
            }
        }
    }
    cout << ans;
    return 0;
}