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

· · 题解

P13108 Alien Rhyme - Solution

Problem Statement

给定 N 个不同的字符串，求出满足以下配对方案的字符串个数：

Analysis

看到要求后缀有关问题，想到字典树算法，只是这里需要从后向前遍历字符串构建字典树。

维护一个数组记录通过每个字符的字符串个数，在查询时从根开始向下贪心找可以使用的字符串即可。

Approach

使用 f 数组记录经过这个点的字符串个数，每次经过时 f[now]\gets f[now]+1 就可以记录。

查询时，从根节点向下进行 \text {DFS} 操作，向下过程中使用 used 先记录当前使用过多少次，回溯到 u 结点时判断 f[u]-used \ge 2。如果是，说明还有后缀未被占用过，used\gets used+2，继续向上。

最后输出 used 就得到了所求答案。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=50005;
int tr[N][30],f[N],cnt;
string s;

int getnum(char x){
    return x-'A'+1;
}

void make_trie(){
    int now=1;
    for(int i=s.size()-1;i>=0;i--){ //枚举后缀 
        int z=getnum(s[i]);
        if(!tr[now][z])
            tr[now][z]=++cnt;
        now=tr[now][z];
        f[now]++; //记录经过过这个点的字符串 
    }
}

int dfs(int u){
    int used=0;
    for(int i=1;i<=26;i++)
        if(tr[u][i])
          used+=dfs(tr[u][i]); //使用过的个数 
    if(u!=1 && f[u]-used>=2)
        used+=2; //匹配一对
    return used;
}

int main(){
    int T;
    cin>>T;
    int cases=1;
    while(T--){
        for(int i=1;i<=cnt;i++){ //初始化 
            fill(tr[i]+1,tr[i]+27,0); 
            f[i]=0;
        }
        cnt=1; //注意要重置字典树
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>s;
            make_trie(); //生成Trie树 
        }
        cout<<"Case #"<<cases<<": "<<dfs(1)<<"\n";
        cases++;
    }
    return 0;
}

Update