给一个字符串 \(S\)
询问 \(Q\) 次，每次给出 \(K\) 个 \(S\) 的子串，现在从这些子串中选出一个子集，问有多少个子集满足集合内任意两个不同的串不存在前缀关系
假设把所有串放到 Trie 树上，方案数可以用一个简单的 DP 算出来
不妨把所有串按照字典序排序（其实就是在 Trie 上的 DFS 序），你可以把压缩后的 Trie （存在分支的节点只有不超过 \(K\) 个）建出来
XVIII Open Cup. Grand Prix of Saratov. I - Prefix-Free Queries
原文：https://www.cnblogs.com/iefnah06/p/12953784.html