BOJ 2112 두 부분 문자열, BOJ 3244 두 부분 문자열2

* BOJ 2112 두 부분 문자열, BOJ 3244 두 부분 문자열2

[분류 : 다이나믹 프로그래밍]

1. B문자열에 대한 모든 가능한 문자 26개에 대해 위치를 오름차순으로 저장하자.

  어떤 문자가 특정 위치 b를 포함한 이후에 존재하는지 안하는지 판단하기 위함이다.

2. 다이나믹 상태

  최대 공통 부분 수열(LCS)을 찾는 것처럼 생각해보자.

  현재 A의 위치 a, 현재 B의 위치 b로 상태 (a, b)에서 문제에서 요구하는 문자열의 길이를 찾아보자.

  1. A[a] 문자를 정답 문자열에 사용하지 않는다.

    이 때는 a위치를 한 칸 이동한다. b는 움직이지 않는다. 여기서 b를 움직여버리면 구조상 B 부분 문자열을 모두 확인할 수 없게 된다.

  2. A[a] 문자를 정답 문자열에 사용한다.

    2-1. A[a]에 해당하는 문자가 B문자열 내에 위치 b를 포함한 이후에 존재한다.

      이 경우엔 A[a] == B[x]인 가장 작은 x를 찾는다. 단, b <= x이다. x가 존재한다는 의미이므로 그 다음 부분 문제를 호출할 때는 길이 하나 증가하여 값을 비교해준다.

    2-2. A[a]에 해당하는 문자가 B문자열 내에 위치 b를 포함한 이후에 존재하지 않는다.

      이 경우엔 A[a]가 B문자열로 구성할 수 없는 부분 문자열의 마지막 문자임을 나타낸다. 이 과정이 가능한 이유는 2-1.에서 b를 움직이지 않기 때문이다.

  

  2.과정에서 인덱스 x의 존재여부는 단순 이분탐색으로 확인할 수 있다.

※ 소스는 3244번 문제가 2112 문제의 확장이기 때문에 3244번 소스만 올립니다.

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N = 2e3;
char A[MAX_N + 1], B[MAX_N + 1];
int dp[MAX_N][MAX_N+1], N, M;
vector<int> pos[26];
int rec(int a, int b) {
    if (a == N) return 1e9;
    int& ret = dp[a][b];
    if (ret != -1) return ret;
    ret = rec(a + 1, b);
    vector<int>& t = pos[A[a] - 'a'];
    auto it = lower_bound(t.begin(), t.end(), b);
    if (it == t.end())
        return ret = 1;
    else
        ret = min(ret, rec(a + 1, *it + 1) + 1);
    return ret;
}
void f(int a, int b) {
    if (a == N) return;
    int& ret = dp[a][b];
    if (ret == rec(a + 1, b))
        f(a + 1, b);
    else {
        printf("%c", A[a]);

        vector<int>& t = pos[A[a] - 'a'];
        auto it = lower_bound(t.begin(), t.end(), b);
        if (it != t.end())
            f(a + 1, *it + 1);
    }
}
int main() {
    memset(dp, -1, sizeof dp);
    scanf("%s%s", A, B);
    N = strlen(A), M = strlen(B);
    for (int i = 0; i < M; i++)
        pos[B[i] - 'a'].push_back(i);
    printf("%d\n", rec(0, 0));
    f(0, 0);
    return 0;
}