hdu 4416 Good Article Good sentence (后缀自动机)

http://acm.hdu.edu.cn/showproblem.php?pid=4416

题意:

给出一个字符串A和n个字符串B,问A的子串中,不在任何一个B中出现的本质不同的子串有多少。

思路:

还是根据len搞事情

我们知道,如果不加任何条件,SAM中一个节点所表示的本质不同的子串数量是st[i].len – st[st[i].link].len

现在加了限制条件。

那么该状态中,有一些长度的字符串就会不满足条件。

我们考虑对母串A构建SAM

那么只需要维护B的所有串,对于某个状态能匹配的最大长度,设为maxlen,那么 长度为[maxlen+1,st[i].len]的字符串可以贡献答案。

如果maxlen为0,则该状态所表示的所有本质不同的子串都可以贡献答案。

维护最大匹配长度 可以参考   spoj-lcs2 解题报告 

有所不同的是不需要在每一个B中都匹配,只需要至少一个匹配就行了,因此是取所有串的最大匹配长度即可。

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz