[백준 3080] 아름다운 이름

문제

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

 

알고리즘

Trie

 

풀이

관찰이  필요한 문제입니다. 예제들을 그림으로 그려 예제 입출력을 이해하도록 합시다. 이를 통해 문제의 답은 

(트라이의 자식 수 + 해당 트라이에서 끝나는 단어)의 팩토리얼들의 곱이라는 점을 알아낼 수 있습니다. 이렇게 문제를 풀게 되면 메모리 초과가 발생하게 됩니다. 

 

Trie?
선형시간에 원하는 문자열을 찾아낼 수 있는 자료구조입니다. 이를 가능케 하는 것은 각각의 트라이마다 모든 문자들을 가리키는 포인터를 저장하고 있기 때문입니다. 이 때문에 많은 메모리를 사용한다는 단점이 있는 자료구조입니다.

 

따라서, 필요하지 않은 문자열을 제거해야합니다. Suffix Array & LCP에서 봤듯이, 주어진 문자열을 정렬한 후 $i$번째 문자와 가장 많은 부분이 겹치는 문자열은 $name [i-1]$과 $name [i+1]$임을 알 수 있습니다. $name [i-1]$와 $name [i]$

의 LCP, $name [i]$와 $name [i+1]$의 LCP 중 큰 값을 $max(cur, prv)$라고 할 때, $i$번째 문자는 $max+1$까지만 트라이에 저장을 해도 답에 영향을 미치지 않음을 알 수 있습니다. child는 max길이 안에서 결정이 나고 max+1에서 끝나나 max+alpha 에서 끝나나 결과는 같기 때문입니다. 

 

코드

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

typedef long long ll;
const int MAX_V = 26;
const int MOD = 1000000000 + 7;
int N;
string S;
vector<string> NAME;
int cache[30];

int facto(int x) {
    if (x == 0) return 1;
    int& ret = cache[x];
    if (ret != -1) return ret;
    ret = (ll)facto(x - 1) * x % MOD;
    return ret;
}
struct Trie {
    Trie* children[MAX_V];
    int child;
    int exist;

    Trie() {
        memset(children, 0, sizeof(children));
        exist = child = 0;
    }
    ~Trie() {
        rep(i, MAX_V) if (children[i]) delete children[i];
    }

    void insert(const char* str, int len) {
        if (len == 0 || !*str) {
            ++exist;
            return;
        }
        int nxt = *str - 'A';
        if (!children[nxt]) {
            children[nxt] = new Trie;
            ++child;
        }
        children[nxt]->insert(str + 1, len - 1);
    }
    ll solve() {
        ll ret = 1;
        if (!child) return 1;
        if (exist) ++child;
        ret = facto(child) * ret % MOD;
        rep(i, MAX_V) if (children[i])
            ret = ret * children[i]->solve() % MOD;
        return ret;

    }
};

int getLen(string& a, string& b) {
    int i = 0;
    while (1) {
        if (!a[i] || !b[i]) break;
        else if (a[i] == b[i]) ++i;
        else break;
    }
    return i;
}

int main() {
    FAST;
    memset(cache, -1, sizeof(cache));
    cin >> N;
    rep(i, N) {
        cin >> S;
        NAME.emplace_back(S);
    }
    sort(NAME.begin(), NAME.end());

    Trie* root = new Trie;
    int cur, prv = 0;
    rep(i, N) {
        if (i == N - 1) cur = NAME[i].size();
        else cur = getLen(NAME[i], NAME[i + 1]);
        root->insert(NAME[i].c_str(), max(cur, prv) + 1);
        prv = cur;
    }
    cout << root->solve();

    return 0;
}