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

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

 Input 

ABRACADABRA

ECADADABRBCRDARA

 

 Output 

5

DP[i][j] = A 문자열의 i번째 문자와 B문자열의 j번째 문자가

공통 부분 문자열의 마지막 문자로 하는 공통부분문자열의 최대 길이

if (A[i] == B[j]) D[i][j] = D[i - 1][j - 1] + 1;

#include <stdio.h>
 
const int LM = 4002;
int an, bn, D[LM][LM], ans;
char A[LM], B[LM];
 
int main() {
    scanf("%s %s", A + 1, B + 1);
    for (int i = 1; A[i]; ++i) {
        for (int j = 1; B[j]; ++j) {
            if (A[i] == B[j]) D[i][j] = D[i - 1][j - 1] + 1;
            if (ans < D[i][j]) ans = D[i][j];
        }
    }
    printf("%d\n", ans);
}

 

문자열 A[] 앞부분의 일부(0개 이상)를 제외하고 B[] 문자열과 비교해봅니다.

같은 자리의 문자가 같다면 가중치를 1로 두고 다르다면 -INF로 둔 수열을 만듭니다.

만들어진 수열을 놓고 연속 부분 최대합을 구합니다.

반대로 B[] 앞부분의 일부(0개 이상)를 제외하고 A[] 문자열과도 비교합니다.

두 가지 경우 중에 최대값을 구합니다.

 

ex) A[]에서 1문자를 제외하고 B[]와 비교 ($ == -INF)

 

시뮬레이션

▶ A[]에서 0문자를 제외하고 B[]와 비교

 

▶ A[]에서 1문자를 제외하고 B[]와 비교

 

▶ A[]에서 2문자를 제외하고 B[]와 비교

 

▶ A[]에서 3문자를 제외하고 B[]와 비교

---

#include <stdio.h>
 
const int LM = 4005;
char A[LM], B[LM];
int alen, blen, ans;
 
inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }
 
void getLcst(char *a, int an, char *b, int bn) {
    int i, len = min(an, bn), val, sum = 0;
    for (i = 0; i < len; ++i) {
        val = a[i] == b[i] ? 1 : -LM;
        if (sum > 0) sum += val;
        else sum = val;
        ans = max(ans, sum);
    }
}
 
int strlen(char *s, int len = 0) {
    while (*s++) len++;
    return len;
}
 
int main() {
    scanf("%s %s", A, B);
    alen = strlen(A);
    blen = strlen(B);
 
    for (int i = 0; i < alen; ++i) {
        getLcst(A + i, alen - i, B, blen);
    }
 
    for (int i = 0; i < blen; ++i) {
        getLcst(B + i, blen - i, A, alen);
    }
 
    printf("%d\n", ans);
}