[백준][5582번][DP] 공통 부분 문자열

공통 부분 문자열

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

<문제>

<코드>

#include <stdio.h>
// a 가 빠르면 0 b가 빠르면 1
int Dp[4001][4001];
 
int main()
{
    int max = 0;
    char A[4001];
    char B[4001];
 
    scanf("%s", A);
    scanf("%s", B);
 
    for (int i = 0; A[i] != 0; i++)
        for (int j = 0; B[j] != 0; j++)
        {
            if (A[i] == B[j]) {
                if (i == 0 || j == 0)
                    Dp[i][j] = 1;
                else
                    Dp[i][j] = Dp[i - 1][j - 1] + 1;
 
                if (max<Dp[i][j])
                    max = Dp[i][j];
            }
        }
    printf("%d\n", max);
    return 0;
}

<문제 푼 요령>

1. Dp[i][j] 는 문자열 A의 i번째 요소와 B의 문자열의 j번째 요소가 비교했을때의 여기서 최대 길이를 저장 한것이다. 

2. 최대길이를 비교하기 위해서는 Dp[i-1][j-1] 의 요소값을 확인해야한다. 왜냐하면 Dp[i][j] 의 즉 A의 i 번째 요소와 B의 j번째 요소가 같을시 이전 Dp[i-1][j-1] 을 확인해서 이전에 까지의 최장길이를 확인해서 추가해야 한다. 

3. 그래서 그 나온 길이값 중에서 최대값을 나타내면 된다.