BZOJ 1590 [Usaco2008 Dec]Secret Message 秘密信息

发布于 2017-06-29  299 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1590

题意:给出 n 条信息,m 条密码,问对于每一条密码,它是多少个信息的前缀或多少个信息是它的前缀


直接对于信息构造字典树,每条信息的终止节点权值加一,这样读入密码的时候走一遍树上路径即可知道多少个信息是它的前缀,它是多少个前缀怎么求呢?记录每个节点字数权值大小即可,答案加上密码终止节点子树权值,但是有一个问题是这样的话如果两个串正好相同会被统计两次,再减去这个点的权值即可。

 


一个非常弱的准退役OIER