[백준 17365] 별다줄

문제

www.acmicpc.net/problem/17365

 

알고리즘

트라이 + DP

 

풀이

문래빗어 사전에 적혀있는 단어수와 그 단어들이 주어졌을 때, 해석하려는 문자열의 가능한 경우의 수를 묻고 있습니다. 해석하려는 문자열을 $str$이라 하겠습니다. (아래에서 언급하는 $str [a:b]$ 는 $str$ a번째 인덱스부터 b번째 인덱스까지의 부분 문자열입니다)

 

$cache [i]$= i+1번째 문자열까지 해석했을 때, 가능한 경우의 수

 

$cache [i+1]$은 다음 상태들의 합입니다. $cache [i]$에서 가능한 개수 * 단어들 중 $str [i+1]$와 매칭 가능한 개수 , cache [i-1] * 단어들 중 $str [i:i+1]$와 매칭 가능한 개수... (매칭이 가능하다는 것은 문래빗어 정의에 따라 각 단어들의 접두사부터 매칭하는 것을 의미합니다)

 

매칭가능한 개수를 찾기 위해선 각 단어들을 순회하며 접두사와 비교를 해야 합니다. 이러한 행동은 시간 초과입니다. 많은 단어들이 주어졌을 때, 선형 시간 안에 원하는 단어를 찾게 해주는 트라이를 활용해야 합니다.

 

즉 $cache [i]$ 를 알고 있다면 우리가 갱신할 수 있는 상태는 트라이의 루트에서부터 탐색 가능한 최대 깊이까지 갱신 가능합니다. 만일 깊이가 4라면 $cache[i+4]$까지 갱신가능합니다. 시간 복잡도는 $str$길이마다 트라이의 루트에서부터 탐색하므로 $O(N*300)$입니다.

 

코드

#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;

const int MOD = 1e9 + 7;
const int MAXL = 200005;
const int MAXN = 26;

int N, sl;
int cache[MAXL];
char str[MAXL];

struct Trie {
    Trie* children[MAXN];
    int cnt;

    Trie() {
        memset(children, 0, sizeof(children));
        cnt = 0;
    }
    ~Trie() {
        rep(i, MAXN) if (children[i]) delete children[i];
    }

    void insert(const char* key) {
        if (*key == 0) return;
        else {
            int nxt = *key - 'a';
            if (!children[nxt]) children[nxt] = new Trie;
            children[nxt]->cnt++;
            children[nxt]->insert(key + 1);
        }
    }
};

int main() {
    FAST;
    cin >> N;
    Trie* root = new Trie;
    rep(i, N) {
        cin >> str;
        root->insert(str);
    }

    cin >> str;
    sl = strlen(str);

    cache[0] = 1;
    for (int i = 0;i < sl;++i) {
        Trie* cur = root;
        for (int j = i;j < sl;++j) {
            int nxt = str[j] - 'a';
            if (!cur->children[nxt]) break;
            cur = cur->children[nxt];
            cache[j + 1] = (cache[j + 1] + (long long)cache[i] * cur->cnt) % MOD;
        }
    }
    cout << cache[sl];
    return 0;
}