[백준] 5582번 - 공통 부분 문자열 (C++) 문제 및 풀이

문제) 백준 - 동적 계획법 - 공통 부분 문자열

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

5582번: 공통 부분 문자열

 

LCS랑 유사한 연속된 공통 문자열을 찾는 문제였습니다. LCS를 풀어봤다면 쉽게 풀 수 있는 문제입니다.

 

C++ 소스코드)

	#include<bits/stdc++.h>
	#define ll long long
	#define INF 987654321
	#define MAX 4002
	using namespace std;
	typedef pair<int, double> p;
	string s1, s2;
	int cache[MAX][MAX] = {0,};
	int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> s1 >> s2;
	int res = 0;
	for (int i = 1; i <= s1.size(); ++i) {
	for (int j = 1; j <= s2.size(); ++j) {
	if (s1[i - 1] == s2[j - 1]) {
	cache[i][j] = cache[i - 1][j - 1] + 1;
	res = max(cache[i][j], res);
	}
	}
	}
	cout << res;
	return 0;
	}

view raw 5582.cpp hosted with ❤ by GitHub