[5582] 공통 부분 문자열, c++

<네이버에서 옮겨온 것>

---

[5582] 공통 부분 문자열

 

한줄 후기 :  내 인생 최대의 적 dp

 

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

5582번: 공통 부분 문자열

 

음 내가 싫어하는 dp문제

dp에도 정을 붙여보려고 풀었다.

 

공통 부분 문자열 성공출처다국어분류

Gold V

다이나믹 프로그래밍

난이도 제공: solved.ac — 난이도 투표하러 가기

 

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	256 MB	6300	2620	2007	43.783%

 

문제

두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오.

어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다.

두 문자열 ABRACADABRA와 ECADADABRBCRDARA의 공통 부분 문자열은 CA, CADA, ADABR, 빈 문자열 등이 있다. 이 중에서 가장 긴 공통 부분 문자열은 ADABR이며, 길이는 5이다. 또, 두 문자열이 UPWJCIRUCAXIIRGL와 SBQNYBSBZDFNEV인 경우에는 가장 긴 공통 부분 문자열은 빈 문자열이다.

 

입력

첫째 줄과 둘째 줄에 문자열이 주어진다. 문자열은 대문자로 구성되어 있으며, 길이는 1 이상 4000 이하이다.

 

출력

첫째 줄에 두 문자열에 모두 포함 된 부분 문자열 중 가장 긴 것의 길이를 출력한다.

 

예제 입력 1

ABRACADABRA ECADADABRBCRDARA

 

예제 출력 1

5

//AC
//BOJ 5582 공통 부분 문자열 
//https://www.acmicpc.net/problem/5582  

#include <iostream>
#include <string> 
#include <algorithm>
using namespace std;
int dp[4001][4001];
int main(){
	string s, s2;
	int max_len = 0;
	cin >> s;
	cin >> s2;
	int len1 = s.size();
	int len2 = s2.size();
	for(int i=0; i<len2; i++){
		if(s[0]==s2[i]){
			dp[0][i] = 1;
		}
	}
	for(int i=0; i<len1; i++){
		if(s[i]==s2[0]){
			dp[i][0] = 1;
		}
	}
	for(int i=1; i<len1; i++){
		for(int j=1; j<len2; j++){
			if(s[i]==s2[j]){
				dp[i][j] = dp[i-1][j-1]+1;
			}

			max_len = max(max_len, dp[i][j]);
		}
	}

	printf("%d", max_len);
	return 0;
} 

 

이 문제는 전형적인 LCS(Longest Common Substring) 문제라 LCS를 공부하고 풀어서 풀이는 쉬었다.

공통 부분 문자열을 찾을 때는

if(s[i]!=s2[j]){
   dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
}
else{
   dp[i][j] = dp[i-1][j-1]+1;
}

 

	B	A	C	B	A
C	0	0	1	0	0
B	1	1	1	2	2
A	0	2	2	2	3
A	0	1	2	2	3

 

이런식으로 두 문자열을 행과 열로 비교해서 dp배열에 저장해주면 된다.

다만 여기서는 연속된 부분 문자열이기 때문에 for문을 돌면서 두 문자가 같을때만 dp에 저장해주면 된다.

다를 때는 연속이 깨진거니 생각할 필요 X