【題目敘述】https://codingcompetitions.withgoogle.com/codejam/round/0000000000051635/0000000000104e05
【解題想法】字典樹 Trie
#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";
}
}