题解

2 条题解

  • 1
    @ 2015-05-10 09:40:59

    首先我们发现这题是一道裸的Aho-Corasick自动机。

    经典做法是对于每个节点维护一个集合,记录走到这个点的时候将有哪些模式串的答案被更新。同时根据AC自动机的特性,更新节点u的同时还要更新节点fail[u]。这种做法能勉强通过40%的数据。

    事实上,对于每个节点,我们可以只记录一个布尔值vis,代表该节点是否在匹配过程中被访问过,访问节点u时仍然需要递归地去访问fail[u]。可以保证每个节点至多被访问1次。与此同时,每次的insert过程中,我们记录:对于字符串i,匹配到长度j的节点编号match[i][j]。接下来对于每个字符串,我们在[0, 100]进行二分查找,每次检查vis[match[i][mid]]是否为真。总的时间复杂度是O(M|S|+N+Mlog100),可以承受。

    这时候其实还有一个小小的优化……
    我们自行生成一个N=10^6的随机数据,会发现对于(几乎)所有的模式串,答案都等于该模式串的长度。由于字符集很小,我们可以认为,对于一个随机的数据,当母串足够长时,所有的模式串几乎都能在母串中找到匹配。故此,当N>10^6时,我采取了这样的策略:对于每个模式串,直接输出它的长度。

    ……然后就过了……最大数据280ms……23333333

  • 0
    @ 2017-03-27 19:24:49

    后缀自动机裸题,但注意只匹配文字的前缀,不用再往pre上转移
    由于n很大,数组开不出来,需要采用楼下神犇的方法过最后一个点Orz
    http://blog.leanote.com/post/okami/vijos

  • 1

信息

ID
1951
难度
7
分类
(无)
标签
递交数
224
已通过
46
通过率
21%
被复制
2
上传者