백준 5582번 공통 부분 문자열

< 백준 5582번 공통 부분 문자열 - 마포 코딩박 >

사용한 알고리즘: DP


 두 문자열 A,B 의 공통 부분 문자열 (연속해야함) 의 길이를 구하는 문제입니다.

문제풀이는 다음과 같습니다.

(1) (코드 7~9)
 '연속된' 공통 문자열을 구해야 하므로
 'dp[0][x][y]: 시작안함, A의 x, B의 y 부터 만들 수 있는 최대 공통 부분 문자열 길이'
 'dp[1][x][y]: 시작함(연속되야함), A의 x, B의 y 에서 연속해서 만들 수 있는 최대 공통 부분 문자열 길이' 로 설정하였습니다.

(2) (코드 11~29)
 과정(1)에서 설정한 dp의 값을 구하는 함수를 만들었습니다.
 시작되었는지(연속되어야 하는지) 여부를 판단하며 만들 수 있는 최대 공통 부분 문자열 길이를 dp로 저장해 가며 탐색했습니다.

	#include <bits/stdc++.h>
	using namespace std;
	#define ll long long
	const int MAX = 4000+1;
	string str1, str2;
	// dp[0][a][b] : 시작 안함, 첫 문자열 a index, 두번째 문자열 b index
	// dp[1][a][b] : 시작함 , 첫 문자열 a index, 두번째 문자열 b index
	int dp[2][MAX][MAX];
	int longestSequence(bool head, int idx1, int idx2){
	// 다봤으면 return
	if(idx1==str1.size() || idx2==str2.size()) return 0;
	int &ret = dp[head][idx1][idx2];
	// 중복 제거
	if(ret!=-1) return ret;
	// 시작안함
	if(head==0){
	ret = max(longestSequence(false,idx1+1,idx2), longestSequence(false,idx1,idx2+1));
	if(str1[idx1]==str2[idx2]) ret = max(ret, 1+longestSequence(true,idx1+1,idx2+1));
	}
	// 시작함. 연속될 수 있는지 판단.
	else{
	if(str1[idx1]!=str2[idx2]) ret = 0;
	else ret = 1+longestSequence(true,idx1+1,idx2+1);
	}
	return ret;
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> str1 >> str2;
	memset(dp,-1,sizeof(dp));
	cout<< longestSequence(0,0,0) << '\n';
	return 0;
	}

view raw BOJ 5582.cpp hosted with ❤ by GitHub