【題解】Google Code Jam 2019 Round 1A C Alien Rhyme

#include <iostream>
#include <cstring>
using namespace std;

int Case, t, n, idx;
string s;
struct s{
    int nxt[26];
    int cnt;
}node[50000];

void build(){
    int cur = 1;
    for (int i = s.length()-1; i >= 0; i--){
        if (node[cur].nxt[s[i]-'A'] == 0){
            node[cur].nxt[s[i]-'A'] = idx;
            cur = idx;
            idx++;
        }
        else cur = node[cur].nxt[s[i]-'A'];
        node[cur].cnt++;
    }
}
int search(int x){
    if (node[x].cnt < 2) return 0;
    else if (node[x].cnt < 4) return 1;
    int ret = 0;
    for (int i = 0; i < 26; i++){
        if (node[x].nxt[i] != 0) ret += search(node[x].nxt[i]);
    }
    node[x].cnt -= ret*2;
    if (node[x].cnt / 2 > 0) ret++;
    return ret;
}

int main() {
    cin >> t;
    while (t--){
        memset(node, 0, sizeof(node));
        cin >> n;
        idx = 2;
        for (int i = 0; i < n; i++){
            cin >> s;
            build();
        }
        int ans = 0;
        for (int i = 0; i < 26; i++){
            if (node[1].nxt[i]) ans += search(node[1].nxt[i]);
        }
        Case++;
        cout << "Case #" << Case << ": " << ans*2 << "\n";
    }
}