hdu 3518 Boring counting (后缀自动机)

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

题意:

给一个字符串,问字符串中,至少出现2次且不相交的本质不同的子串有多少个。本质不同给的子串是说存在至少一位的字母不同。

思路:

考虑SAM

SAM上的一个节点表示的是一段长度从[st[st[i].link],len+1,st[i].len]的字符串。

考虑其right集合,如果right集合中最大的r设为rightmost,最小的r设为leftmost.

那么如果rightmost-leftmost+1 > st[i].len ,说明什么呢?

说明该状态所表示的最长的字符串能够至少放下两个而不重叠。

即从[leftmost-st[i].len+1,leftmost]一段 和 从[rightmost-st[i].len+1,rightmost]一段。

如果最长的能放下,那么其他的也一定能放下。因此对答案贡献为st[i].len – st[st[i].link].len

如果rightmost-leftmost+1<=st[i].len,也就是rightmost-leftmost<st[i].len

这个时候长的字符串因为重叠了不能出现2次,但是短的字符串仍然可以贡献答案。

考虑如下图:

此时对答案的贡献为rightmost-leftmost+1 – (st[st[i].link].len+1),化简得到rightmost-leftmost-st[st[i].link].len

综合2种情况,SAM中每个节点对答案的贡献是 min(rightmost-leftmost,st[i].len)-st[st[i].link].len

需要注意的是只有在st[i].link存在并且rightmost-leftmost>st[st[i].link].len 时 才更新答案

leftmost可以在构建的时候直接求出,rightmost用拓扑序更新下即可。

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz