【问题描述】
有一种特殊的集合叫做 PFS（Prefix Free Set）集合。 一个 PFS 集合由若干字符串构成，且不存在一个字符串是另一个字符串的前缀。空集也 被看作是 PFS 集合。 例 如 {"hello"} 和 {"hello", "goodbye", "giant", "hi"} 是 pfs 集合，但 {"hello","hell"} 和{"great","gig","g"} 不是。 现在给你一个集合，请你求出它的子集是 PFS 集合的子集个数对 9191 取模后的答案。
【输入格式】 输入数据第一行一个整数 n，表示集合里元素的个数。 以下 n 行，每行一个非空字符串 s，仅包含小写英文字母，表示集合中的元素。数据保 证不存在两个相同的字符串。
【输出格式】 输出一个正整数 ans，表示对 9191 取模后的答案。
【输入样例】
3
hello
hi
hell
【输出样例】 6
【输入输出解释】 除了 {"hell","hello"} 和 {"hi","hello","hell"} 两种情况外，其余情况均是 PFS 集合。
【数据范围】 对于 30%的数据，n≤20； 对于 100%的数据，1≤n≤50000，字符串长度不大于 50。
string自带 < 运算符，因此可以用sort排序，自动将string数组排为字典序。
同时，string的find函数可以当做kmp来使用，在某些情况下效果绝佳，譬如本题。
将输入的字符串字典序排序后，倒序推导
令 F[i]表示第i~n个字符串可能的组合数量，可以得到状态转移方程：F[i]=F[i+1]+F[j]，其中 j 是在i之后的、不以i为前缀的字符串的下标。（1<j<=n+1）
同时注意到，空集也是一个合法的解，因此可以置 F[n+1]=1，这将在后续结果中加上空集这一个解。
想什么？
可以从题意得知，若 i 是 j 的前缀，则 i 与 j 最多选其一放进同一集合中。因此首先得到一部分的方程：F[i]=F[j]，这表示在集合里面i与j是等价的，可互相替换但不能共存，也可以都不存在。
若 i 不是 j 的前缀，那么 i 与 j 不等价，他们可以同时放进一个集合中。
解释方程？
如果 i 不是 i + 1 的前缀，那么 j = i + 1 ，即 F[i]=F[j]+F[j] ，这意味着 i 加入集合，或不加入两种情况。
如果 i 是 i+1 的前缀，那么 i 与 i + 1 等价，方案数相同；同时 i 是可以加入任意 j 的集合中的，所以 F[i] = F[i+1] + F[j]
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 template inline void read(T &_a){ 8 bool f=0;int _ch=getchar();_a=0; 9 while(_ch<'0' || _ch>'9'){ if(_ch=='-')f=1;_ch=getchar();}10 while(_ch>='0' && _ch<='9'){_a=(_a<<1)+(_a<<3)+_ch-'0';_ch=getchar();}11 if(f)_a=-_a;12 }13 14 const int maxn=50010,modx=9191;15 int n,dp[maxn];16 string str[maxn];17 18 int main()19 {20 read(n);21 for (register int i=1;i<=n;++i) cin>>str[i];22 sort(str+1,str+n+1);23 dp[n+1]=1; // 空集24 for (register int i=n,j;i;--i)25 {26 j=i+1;27 while(!str[j].find(str[i])&&j<=n) ++j;28 dp[i]=(dp[i+1]+dp[j])%modx;29 } 30 printf("%d",dp[1]);31 return 0;32 }