문제 소개 📌

문제 링크 📢

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

문제 풀이 📝

두 문자열이 주어졌을 때, 가장 긴 공통 부분 문자열을 찾으려면 일단 두 문자열의 길이만큼의 2차원 dp배열을 선언한다.
이후 for문을 통해 두 문자열의 문자를 하나씩 비교해가면서 만약 같은 문자가 나왔다면 dp배열에 표기를 한다.
두 문자열만 놓고 봤을 때 바로 이전의 문자에 대한 정보는 i, j가 각각 문자열의 현재 위치 인덱스이기 때문에 dp[i-1][j-1]에 존재할 것이다. 따라서 같은 문자를 발견했을 때 조건을 주어 dp[i][j] = dp[i-1][j-1] + 1와 같이 dp배열을 갱신하면서 그 중 가장 긴, 즉 가장 큰 값을 구하면 AC를 받을 수 있다.

코드

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int dp[4005][4005];
int main()
{
	int ans = 0;
	string str1, str2;
	cin >> str1 >> str2;
	for (int i = 1; i <= str1.size(); i++)
	{
		for (int j = 1; j <= str2.size(); j++)
		{
			if (str1[i-1] == str2[j-1])
			{
				dp[i][j] = dp[i - 1][j - 1] + 1;
				ans = max(ans, dp[i][j]);
			}
		}
	}
	cout << ans;
	return 0;
}