绿书模拟day10 单词前缀

【题目描述】
一组单词是安全的,当且仅当不存在一个单词是另一个单词的前缀,这样才能保证数据不容易被误解,现在你手上有一个单词集合s,你需要计算有多少个自己是安全的。
注意空集永远是安全的。
【输入格式】
第一行一个数n,表示集合打下,以下n行,每行一个由小写字母构成的字串
【输出格式】
安全子集的个数
【输入样例】
3
hello
hell
hi
【输出样例】
6
【数据规模】
对于30%的数据,满足1<=n<=10;
对于100%的数据,满足1<=n<=50,字符串长度<=50,没有两个字串是完全相同的。

/*
说一下这个题目的思路,首先发现这个统计个数非常大,常规搜索搜不出几个点来,考虑动态规划,设计状态,考虑单词前缀可以用字典树方便表示,联想到树形dp,假设f[x]表示以字典树x节点为根节点的子树能有多少方案数,首先考虑空集,只有一个单词的时候可以只有它一个或一个空集,往上走,假设一个节点有若干儿子,很容易发现一个性质,这些儿子的方案无论怎样混合,都不会发生危险(根据定义根节点往上的单词不予考虑),这样相互根据乘法原理可以相互乘起来(因为由空集的存在,所以空集和只去某几个子节点的方案都被考虑进来),这样就行了
*/
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
const int maxn = ;
const int sed = ,Sed = ,mod = ,Mod = ;
int read(){
int x=,f=;
char ch=getchar();
while(!(ch>=''&&ch<='')){if(ch=='-')f=-;ch=getchar();};
while(ch>=''&&ch<=''){x=x*+(ch-'');ch=getchar();};
return x*f;
}
int n,sz = ,a[][];
ll am[],rec[],ans[],tmp,cal;
char s[maxn][maxn];
void ins(int pos){
int now=,l=strlen(s[pos]+);
for(int i=,t=s[pos][i]-'a'+;i<=l;i++,t=s[pos][i]-'a'+){
if(a[now][t]) now=a[now][t];
else now=a[now][t]=++sz;
}
am[now]++;
}
void dfs(int x){
rec[x] = ;
for(int i = ;i <= ;i++){
if(a[x][i]){
dfs(a[x][i]);
rec[x] *= rec[a[x][i]];
}
}
rec[x] += am[x];
}
int main(){
freopen("dc.in","r",stdin);
freopen("dc.out","w",stdout);
cin>>n;
for(int i = ;i <= n;i++){
scanf("%s",s[i]+);
ins(i);
}
dfs();
cout<<rec[];
return ;
}
上一篇:JDBC排序数据实例


下一篇:【翻译】Chemkin - Chapter 1