[백준 2401] 최대 문자열 붙여넣기

문제

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

알고리즘

KMP, 동적 계획법

 

풀이

직관적인, 나이브한 방법으로 생각을 해봅시다. 짧은 문자열들을 긴 문자열의 각 위치마다 일일이 매칭을 시도해보는 방법을 떠올릴 수 있습니다. 긴 문자열 $L$에서 짧은 문자열$I$이 시작할 수 있는 위치를 찾는데 한 개가 아닌 $N$개의 문자열에 대해서 해야 합니다. 우리는 이 방법을 최적화할 수 있는 방법을 알고 있습니다. 긴 문자열에서 짧은 문자열을 찾는 알고리즘. 즉 KMP입니다. 매칭은 빠르게 했으니 일일이 시도하는 문제는 동적 계획법을 통하여 풀 수 있습니다. 시간 복잡도는 $O(N(L+I)+NL)$입니다.

 

매칭한 결과를 저장할 수 있는 효율적인 방법을 생각해보도록 합시다. 처음에 저는 벡터로 저장을 했다가 메모리 초과를 받았습니다. bool 2차원 배열로 해결 가능하며, 메모리를 더 줄이기 위하여 bitset을 사용했습니다.

 

++

바텀업으로 동적 계획법을 설계한다면, 속도나 메모리 측면에서 더 많은 효과를 볼 수 있습니다. 

 

 

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;


string S, W;
bitset<100005> can_use[505];
int N, s;
int fail[10001], len[10001], cache[100001];

int solve(int idx) {
    if (idx == s) return 0;
    int& ret = cache[idx];
    if (ret != -1) return ret;
    ret = solve(idx + 1);
    rep(i, N) {
        if (can_use[i][idx]) ret = max(ret, len[i] + solve(idx + len[i]));
    }
    return ret;
}

int main() {
    FAST;

    memset(cache, -1, sizeof(cache));
    cin >> S >> N;
    s = S.size();

    rep(k, N) {
        cin >> W;
        memset(fail, 0, sizeof(fail));

        int w = W.size();
        len[k] = w;

        for (int i = 1, j = 0;i < w;++i) {
            while (j && W[i] != W[j]) j = fail[j - 1];
            if (W[i] == W[j]) fail[i] = ++j;
        }

        for (int i = 0, j = 0;i < s;++i) {
            while (j && S[i] != W[j]) j = fail[j - 1];
            if (S[i] == W[j]) {
                if (j == w - 1) {
                    can_use[k][i - j] = true;
                    j = fail[j];
                }
                else ++j;
            }
        }
    }
    cout << solve(0);
    return 0;
}