5582번: 공통 부분 문자열

메모리

시간

63532 KB

64 ms

Code

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int main()
{
	char	one[4002];
	char	two[4002];
	scanf("%s", one);
	scanf("%s", two);
	int n = strlen(one);
	int m = strlen(two);
	int check = 0;
	int result[n + 1][m + 1] = {0,};

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (one[i] == two[j])
			{
				result[i + 1][j + 1] = result[i][j] + 1;
				if (check < result[i + 1][j + 1])
					check = result[i + 1][j + 1];
			}
		}
	}
	printf("%d", check);
}

문제 풀이

두 문자열 크기의 이차원 배열 선언으로 문자열 일치할 시에 왼쪽 대각선 인덱스에서 1을 더해가는 점화식으로 풀이하였다. check에 가장 높은 값을 갱신하여 출력하였다.