题解：P13108 [GCJ 2019 #1A] Alien Rhyme

· · 题解

居然还没有题解，赶紧来一发。
其实和正常字典树没什么区别，只是这里要求后缀，所以我们把字符串倒过来加入字典树。
如何得出答案？
其实也不难。后续遍历整棵字典树，如果能匹配就答案 +2，然后这个节点的父节点的计数数组要全部 -2，也就是减去以这个节点为根节点的子树的答案。
至于为什么要后续遍历，样例的第 3 个小数据就给出答案了。
因为每个重音后缀只能匹配两个字符，而先序遍历可能会找到多个有相同的重音后缀的字符。虽然稍微处理一下也可以过，但是后序遍历更简单。

code

#include<iostream>
using namespace std;
int trie[5005][60] , len , cnt[5005] , n;
void insert(string s){
    int p = 0;
    for(int i=s.size()-1;i>=0;i--){
        int x = s[i] - 'A';
        if(trie[p][x]==0)trie[p][x] = ++len;
        p = trie[p][x] , cnt[p]++;
    }
}
int solve(int i){
    int res = 0;
    int tmp = 0;
    for(int c=0;c<26;c++){
        if(trie[i][c]){
            res += solve(trie[i][c]);
            tmp += cnt[trie[i][c]] - res;
        }
    }
    if(i!=0&&cnt[i]-res>=2)res += 2;
    return res;
}
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int T;cin >> T;
    for(int x=1;x<=T;x++){
        for(int i=0;i<=len;i++)for(int j=0;j<26;j++)trie[i][j] = 0 , cnt[i] = 0;
        len = 0;
        cin >> n;
        for(int i=1;i<=n;i++){
            string s;cin >> s;
            insert(s);
        }
        cout << "Case #" << x << ": " << solve(0) << "\n";
    }
    return 0;
}

话说为什么时限20s