robot_rhyme.cpp

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(i=a;i<b;i++)
#define rrep(i,b,a) for(i=b;i>=a;i--)
#define ld long double
#define ll long long
#define umapi unordered_map<int,int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int> 
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define pb push_back
#define mk make_pair
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);

template <typename T>
ostream& operator << (ostream& stream, const pair<T,T> &p) {
    return stream<<"("<<p.first<<","<<p.second<<") ";
}

int sz;
const int mxSZ = 1000*50+2;
int trie[mxSZ][26], par[mxSZ], visits[mxSZ];
int root;

int getNode(){
    return ++sz;
}

void insertTrie(string s){
    int len = s.length();
    int t = root;
    for(int i = 0; i < len; i++){
        int c = s[i] - 'A';
        if(trie[t][c]==0){
            int new_node = getNode();
            par[new_node] = t;
            trie[t][c] = new_node;
        }
        t = trie[t][c];
        visits[t]++;
    }
}

void solve(){
    int n;
    cin>>n;
    for(int i = 0; i < n; i++){
        string s;
        cin>>s;
        reverse(s.begin(), s.end());
        insertTrie(s);
    }

    int ans = 0;
    for(int i = sz; i > 0; i--){
        // cerr<<visits[i]<<" ";
        if(visits[i] < 2) continue;

        ans += 2;
        int v = i;
        while(v){
            visits[v] -= 2;
            v = par[v];
        }
    }

    cout<<ans<<"\n";
}

int main(){
    fast 
    int T;
    cin>>T;
    int t;
    rep(t, 1, T+1){
        cout<<"Case #"<<t<<": ";
        solve();
        sz = root = 0;
        memset(trie, 0, sizeof(trie));
        memset(visits, 0, sizeof(visits));
        memset(par, 0, sizeof(par));
    }
    return 0;
}