BOJ-5582-공통 부분 문자열

[changicho]

5582. 공통 부분 문자열

링크

난이도	정답률(_%)
Silver I	43.342

설계

메모이제이션

dp를 먼저 전부 0으로 초기화한다.

string A,B를 입력 받는다고 했을 때, A[i]와 B[j]가 같은 경우

dp[i+1][j+1] = dp[i][j] + 1

dp 배열의 크기는 기존 정 사이즈보다 1 크게 설정해야 한다.

정리

내 코드 (ms)	빠른 코드 (ms)
60

고생한 점

코드

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

string A, B;

int dp[4002][4002] = { 0, };	// 문자열의 최대 길이는 4000

void solution() { 
	cin >> A >> B;

	int answer = 0;

	for (int i = 0; i < A.length(); i++) {
		for (int j = 0; j < B.length(); j++) {
			if (A[i] == B[j]) {
				dp[i + 1][j + 1] = dp[i][j] + 1;

				answer = max(answer, dp[i + 1][j + 1]);
			}
		}
	}

	cout << answer << "\n";
}

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

	solution();

	return 0;
}