[백준 5582] 공통 부분 문자열(C++)

📕문제

---

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

어떤 문자열 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 이하이다.

📕출력

---

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

 

🔎문제 해석

---

 

처음에는 최장공통부분수열과 헷갈려서 많이 헤맸다..

최장 공통부분 수열은 연속적이 아니어도 되는데 최장 공통부분 문자열은 연속적인 것을 저장해야 하기 때문에 두 알고리즘 자체가 다르다.

최장 공통부분 수열과 최장 공통부분 문자열의 차이는 아래 링크를 달아두겠다.

요기~~!!

두 문자열을 비교해서 연속적인 부분수열의 최대의 길이를 찾는다.

말 그대로 비교하는 두 문자열의 문자(str1[i],str2[j])가 같을 시 (i+1, j+1)해서 다음칸을 비교한다.

만약 다를시 그대로 넘어가고 같을 시 계속 쭉쭉쭉 대각선 방향으로 진행한다.

계속 DP의 값을 최대값으로 경신시켜주면 쉽게 풀릴 문제이다.

DP로 접근한다는 생각만 한다면 쉽게 풀릴 문제이다.

 만약 이문제를 응용해서 저 문자열을 출력하라고 한다면

최댓값인 위치를 기록해서 그 위치에서부터 값만큼 왼쪽 위 대각선으로 이동시켜주면서 그때의 문자를 문자열에 넣고 역순으로 출력하면 해당 문자열이 된다.!!

연속적인 문자열이기에 대각선 방향만 생각하면 돼서 쉬운 문제였다.

처음에는 조금 헤맸지만,,ㅎㅎ

💻코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>

using namespace std;
string str1, str2;
int answer = 0;
vector<vector<int>> dp;
int main()
{
    //문자열 2개 선언
    cin >> str1 >> str2; //문자열 2개 입력받기
    int size = str1.length(), Size = str2.length();
    dp.resize(size + 1, vector<int>(Size + 1, 0)); // 2차원 배열 초기화.
    for (int i = 1; i <= size; i++)
    {
        for (int j = 1; j <= Size; j++)
        {
            if (str1[i - 1] == str2[j - 1]) //문자열이 같아요
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            answer = max(answer, dp[i][j]);
        }
    }

    cout << answer;
}

✔느낀점

• 갑자기 DP가 튀어나와서 놀랬다.
• 다른 DP문제보단 쉬운 문제였는데 DP로 접근한다는 생각이 난이도를 결정할듯하다!
• 최장 공통부분 문자열과 최장 공통부분 수열은 다르다~~