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

CPP

#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

Update on 2025/10/23：修改了数组的大小，感谢@edu1049139032
Update on 2025/11/24：注意到未重置 $cnt=1$ ，导致内存溢出了，感谢@WangYangyu

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

文章操作