🙇‍♀️[Gold V] 공통 부분 문자열 - 5582

문제 링크

성능 요약

메모리: 64800 KB, 시간: 76 ms

분류

다이나믹 프로그래밍, 문자열

제출 일자

2024년 6월 9일 14:14:01

문제 설명

두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오.

어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다.

두 문자열 ABRACADABRA와 ECADADABRBCRDARA의 공통 부분 문자열은 CA, CADA, ADABR, 빈 문자열 등이 있다. 이 중에서 가장 긴 공통 부분 문자열은 ADABR이며, 길이는 5이다. 또, 두 문자열이 UPWJCIRUCAXIIRGL와 SBQNYBSBZDFNEV인 경우에는 가장 긴 공통 부분 문자열은 빈 문자열이다.

입력

첫째 줄과 둘째 줄에 문자열이 주어진다. 문자열은 대문자로 구성되어 있으며, 길이는 1 이상 4000 이하이다.

출력

첫째 줄에 두 문자열에 모두 포함 된 부분 문자열 중 가장 긴 것의 길이를 출력한다.

🚀풀이

알고리즘 설명 2차원 배열 생성:

두 문자열의 길이를 각각 m과 n이라고 할 때,

(m+1)×(n+1) 크기의 2차원 배열 dp를 생성합니다.
dp[i][j]는 첫 번째 문자열의 i번째 문자까지와 두 번째 문자열의 j번째 문자까지의 공통 부분 문자열의 길이를 저장합니다.

기본값 설정:

dp 배열의 첫 행과 첫 열은 모두 0으로 초기화됩니다. 이는 공통 부분 문자열의 길이가 0임을 의미합니다.

배열 채우기:

두 문자열의 각 문자를 비교하며 배열을 채웁니다.
만약 첫 번째 문자열의 i번째 문자와 두 번째 문자열의 j번째 문자가 같다면, dp[i][j] = dp[i-1][j-1] + 1로 설정합니다.
문자가 같지 않다면, dp[i][j] = 0으로 설정합니다.
공통 부분 문자열의 길이를 갱신할 때마다 최장 길이를 기록해둡니다.

결과 반환:

dp 배열에서 최장 공통 부분 문자열의 길이를 찾습니다.

image

🚀코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <climits>

using namespace std;

int longestCommonSubstring(string s1, string s2) 
{
    int m = s1.length();
    int n = s2.length();

    // DP 테이블 초기화
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    int max_length = 0; // 가장 긴 공통 부분 문자열의 길이

    for (int i = 1; i <= m; ++i) 
    {
        for (int j = 1; j <= n; ++j) 
        {
            if (s1[i - 1] == s2[j - 1]) 
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                max_length = max(max_length, dp[i][j]);
            }
            // 연속하지 않은 경우 0으로 초기화
            else 
            {
                dp[i][j] = 0;
            }
        }
    }

    return max_length;
}

void solve()
{
    string s1, s2;
    cin >> s1 >> s2; // 입력

    // 결과 출력
    cout << longestCommonSubstring(s1, s2) << endl;
}

int main()
{
	FILE* stream;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen_s(&stream, "input.txt", "rt", stdin);

	solve();

	return 0;
}

참고