취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 5582번 문제인 공통 부분 문자열이다.

문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/5582 

longest common substring을 구하는 문제이다.

longest common substring을 구하는 방법에는 1) suffix tree를 이용하거나 2) 2차원 DP배열을 채워나가는 방법 등이 있다.

suffix tree는 어려운 자료구조이므로 여기서는 2차원 DP배열을 채워나가는 방법으로 풀어보자.

두 문자열을 s1, s2라 하자. 이 때, dp[i][j]를 "s1의 i번째 글자로 끝나는 문자열과 s2의 j번째로 끝나는 문자열 중 일치하는 문자열의 최대 길이"로 정의하자.

s1[i]와 s2[j]가 일치한다면 각 두 문자열에서 마지막 글자를 지운 문자열의 정보를 dp[i-1][j-1]에 기록해뒀으므로 dp[i][j]는 dp[i-1][j-1] + 1로 계산할 수 있고, 불일치한다면 몇 글자의 부분문자열을 취해도 마지막 글자가 다르므로 dp[i][j] = 0이 된다.

이 DP를 구현해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;

string s1, s2;
int s1len, s2len;
int dp[4001][4001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int mx = 0;
	cin >> s1 >> s2;
	s1 = " " + s1, s2 = " " + s2;
	s1len = s1.length(), s2len = s2.length();
	for (int i = 1; i < s1len; i++) {
		for (int j = 1; j < s2len; j++) {
			if (s1[i] == s2[j]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
				mx = max(mx, dp[i][j]);
			}
		}
	}

	cout << mx;
}