我们这样定义一组单词的安全性：当且仅当不存在一个单词是另一个单词的前缀。这样才能保证数据不容易被误解。 现在你手上有一个单词集合 S ，你需要计算有多少个子集是安全的。注意空集永远是安全的。
第 1 行一个整数 n ，表示集合的大小，以下 n 行，每行一个 “a” ... “z” 构成的字符串。
一个数表示安全子集的个数。
输入
3 hello hell hi输出
6【数据范围】 对于 30% 的数据，满足：1≤n≤10; 对于 100% 的数据，满足：1≤n≤50；字符串长度≤50；没有两个字符串完全相同。
解题报告：
首先建立字母树，字母树上的一个节点就代表从根到这个节点上的一个单词。 如果选择了某个点，就不能选择任何以这个点为根的子树中的任意点。 用DP计算方案数。 f[i] 表示取节点 i 或者其子孙的方案，转移方程就是：
其中si表示 i 的儿子。
时间复杂度：O(|len|)
#include<stdio.h> #include<cstring> int tree[2501][26]; bool v[2501]; int n,tot=1; char s[50]; inline void insert(char *s) { int cnt=1; for(int i=0;i<strlen(s);++i) { if(tree[cnt][s[i]-'a']==0) { tot++; tree[cnt][s[i]-'a']=tot; } cnt=tree[cnt][s[i]-'a']; } v[cnt]=1; } inline long long ca(int root) { long long t=1; for(int i=0;i<=25;++i) if(tree[root][i]>0) t*=ca(tree[root][i]); return t+v[root]; } int main() { scanf("%d\n",&n); for(int i=1;i<=n;++i) { gets(s); insert(s); } printf("%lld\n",ca(1)); return 0; } #include<stdio.h> #include<cstring> #include<string> #include<algorithm> int n,first[51],next[51]; long long w[51][2]; char c[51][50]; struct node{ int pos,len; }s[51]; inline bool comp(const node&a,const node&b) { return a.len<b.len; } inline bool con(int x,int y) { int len=std::min(s[x].len,s[y].len); x=s[x].pos; y=s[y].pos; for(int i=0;i<len;++i) if(c[x][i]!=c[y][i]) return false; return true; } inline void ca(int x) { w[x][0]=1; long long tot=1; for(int y=first[x];y;y=next[y]) { ca(y); tot*=w[y][0]+w[y][1]; } w[x][1]=tot; } int main() { scanf("%d\n",&n); for(int i=1;i<=n;++i) { gets(c[i]); s[i].len=strlen(c[i]); s[i].pos=i; } std::sort(s+1,s+n+1,comp); for(int i=1;i<=n;++i) { int j; for(j=i-1;j>=1;--j) if(con(j,i)) break; next[i]=first[j]; first[j]=i; } ca(0); printf("%lld\n",w[0][1]); return 0; }