5582: 공통 부분 문자열

공통 부분 문자열 성공다국어

한국어   

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

256 MB

11867

4823

3762

42.882%

문제

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

어떤 문자열 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

예제 입력 2 복사

UPWJCIRUCAXIIRGL
SBQNYBSBZDFNEV

예제 출력 2 복사

0

출처

 

 

#include<iostream>
#include<string>
using namespace std;
int dp[4001][4001];
int main() {

	string s1, s2;
	cin >> s1 >> s2;

	for (int i = 0; i < s1.size(); i++) {
		for (int j = 0; j < s2.size(); j++) {
			if (s1[i] == s2[j]) {
				if (j > 0&& i>0) {
					if (dp[i - 1][j - 1] != 0)
						dp[i][j] = dp[i - 1][j - 1] + 1;
					else
						dp[i][j] = dp[i][j] + 1;
				}
				else dp[i][j] = dp[i][j] + 1;
			}
		}
	}
	int max = 0;
	for (int i = 0; i < s1.size(); i++) {
		for (int j = 0; j < s2.size(); j++) {
			if (max < dp[i][j])max = dp[i][j];
		}
	}
	cout << max;
	return 0;
}

dp문제인데 재밌게풀었다.

 

가로반전해야하는데 하는 방법을 모른다..ㅠ