5582번 공통 부분 문자열

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

LCS 알고리즘하고 비슷했다.

다만, 

나는 LCS처럼 접근하려고 표를 그리면서 구현하였었는데

즉, LCS처럼 값을 누적하면서 표를 작성하였는데,

같을 때의 처리가 애매해서 다른 코드를 참고하였다.

그 코드는 아래의 표처럼 

오직 같을 때만 [행-1][열-1]의 값에 +1을 해주었다.

생각해보니 공통 부분 문자열의 최댓값을 구하는 것이므로

따로 누적(?)할 필요가 없었다.

 

초록색이 답이다.

#include <bits/stdc++.h>
 
using namespace std;
 
int dp[4040][4040] = { 0, }, answer = 0;
 
string str1, str2;
 
int main(void)
{
    string input1, input2;
 
    cin >> input1 >> input2;
 
    str1 = '0' + input1;
    str2 = '0' + input2;
 
    for (int i = 0; i < str1.length(); i++)
        for (int j = 0; j < str2.length(); j++)
        {
            if (i == 0 || j == 0)
            {
                dp[i][j] = 0; // dp가 전역 변수여서 굳이 안 해도 되지만, 써보았다.
                continue;
            }
 
            if (str1.at(i) == str2.at(j)) dp[i][j] = dp[i - 1][j - 1] + 1;
 
            answer = max(answer, dp[i][j]);
        }
 
    printf("%d\n", answer);
 
    return 0;
}