hdu 5558 | 2015ACM/ICPC亚洲区合肥站 G Alice’s Classified Message (后缀自动机)

题目链接:

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

题意:

说了一大堆。。其实就是询问位置i开始的后缀和以位置[0…i – 1]开始的所有后缀中最大匹配的公共前缀长度

思路:

这个动态的过程很容易想到SAM啊。。

所以就一边匹配。。一边构建SAM就好了。。

需要注意的是,如果有多个最长,需要输出最左边的位置。

因此多维护一个leftmost,表示某个字符串第一次出现的结尾的位置。

 

 

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz