백준 5582 공통 부분 문자열

백준 5582 공통 부분 문자열

---

저번 주 스터디 문제였는데 어려울거 같아서 넘어갔다가, 오늘 사람들이 나누는 이야기를 엿듣고 보니 그렇게 어렵진 않을거 같아서 도전해 보았다. 실제로도 좀 힌트를 가지고 접근하니 할만 하다!

• dp 를 이용해 풀었고, 공통 부분 문자열이므로 현재 만약 첫번째 문장 인덱스 i 와 두번째 문장 인덱스 j 가 가리키는 값이 서로 같은 문자라면, 그 이전의 dp 값에 +1 해주면 된다.

• 0 보다 큰 경우에 대해서만 따로 값 1을 주겠다는 예외 처리를 해주었고, 그 외에 따로 신경 써야 할 부분은 없었다.

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

using namespace std;

int dp[4002][4002];
int max_val = 0;
int main()
{
    string a, b;
    cin>>a;
    cin>>b;

    for (int i = 0; i < a.size(); i++)
    {
        for (int j = 0; j < b.size(); j++)
        {
            if (a[i] == b[j])
            {
                if (i >= 1 && j >= 1)
                {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    max_val = max(dp[i][j], max_val);

                } else
                {
                    dp[i][j] = 1;
                    max_val = max(dp[i][j], max_val);
                }
            }
            else
            {
                dp[i][j] = 0;
            }


        }
    }
    cout<<max_val<<"\n";
    return 0;
}