「Codeforces 1063F」String Journey
第一篇算法相关
第一次自己想sam
题意
给出一个长度为$n$的字符串$s$。
如果一个字符串序列$t_1,\dotsc,t_k$,$\forall1<i\le k$,$t_i$是$t_{i-1}$的一个子串,且长度严格小,那么称这个字符串序列是一个journey
。
一个journey
的长度是其中字符串的数量
求最长的journey
,满足存在字符串序列$u_1,\dotsc,u_{k+1}$(可以为空),使$s=u_1t_1u_2t_2\cdots u_kt_ku_{k+1}$。
分析
- 观察:存在最长的journey $t$,满足$|t_i|=|t_{i-1}|-1$,即长度每次减少1
显然这可以通过删减一定字符得到
- 观察:若存在以$s$中的第$i$个位置开头的长度为$k$的journey,那么存在以该位置开头的长度为$t,1\le t\le k$的journey
这也可以删除一定字符得到
然后考虑从右向左dp,令$f_i$表示以$s$中第$i$个位置开头的最长的journey的长度。
$f_i$是可以二分的,但是并不好检验
- 观察:$f_{i+1}\ge f_i-1$
这也可以通过删除一定字符得到
移项得$f_i\le f_{i+1}+1$
因此不需要二分,由于均摊的性质,直接推下来,总检验次数是线性的
- 观察:在dp过程中,能被转移的位置$(\ge i+f_i-1)$单调不严格左移
在从$i+1$转移到$i$时,能被转移的位置不变:$i+f_i=i+f_{i+1}-1=(i+1)+f_{i+1}$
在检验$f_i$失败的时候,$f_i$减小,$i+f_i-1$也减小
于是需要数据结构维护
插入一个位置
检验是否有位置$j$与当前的$i$满足最长公共前缀$lcp(s[i..n],s[j..n])\ge f_i-1$,且$f_j\ge f_i-1$
考虑使用sam+线段树
对$s$的反串建sam,插入一个位置$p$的时候,从这个位置对应的parent树终止节点向上跳到最深的一个能表示出长度$f_p$的节点$u$,($len_u\ge f_p$,$len_u$表示$u$能表示的最长字符串)。
$u$子树中所有的节点表示的串和$u$的最长公共前缀$\ge f_p-1$。
并且对于$u$的任意祖先$v$,$v$的子树中所有节点表示的串和$u$的最长公共前缀$\ge len_v$。
这些可以转化到dfs序上的区间取max,用线段树维护
而检验一个$f_p$的时候只要查询覆盖i对应的终止节点处的最大值是否$\ge f_p-1$
考虑到更新$u$的祖先$v$的时候复杂度并不优秀,但是更新的值是$len_v$,这只和$v$自身有关,打个标记避免重复,可以做到$\mathcal O(n)$次
字符集大小为常数,总复杂度$\mathcal O(n\log n)$
代码
1 |
|
「Codeforces 1063F」String Journey