BOJ 5582 공통 부분 문자열

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <functional>

typedef long long int ll;
using namespace std;
#define INF 1234567890
#define N 200000

const int LIMIT = 1e+9;
string s1, s2;
int dp[4005][4005];
int res;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> s1 >> s2;
	
	for (int i = 1; i <= s1.length();  i++) {
		for (int j = 1; j <= s2.length();  j++) {
			dp[i][j] = s1[i - 1] == s2[j - 1] ? 1 + dp[i - 1][j - 1] : 0;
			res = max(res, dp[i][j]);
		}
	}
	cout << res;
	return 0;
}

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

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	256 MB	4573	1916	1446	44.879%

문제

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

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

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