P3435 [POI2006]OKR-Periods of Words题解

题意$:$

给定一个字符串$s$$,$

其中$s_1$$s_2$……$s_i$是$s_1$$s_2$……$s_j$的前缀$($$条件1$$)$

$s_1$$s_2$……$s_j$是$s_1$$s_2$……$s_i$$s_1$$s_2$……$s_i$的前缀$($$条件2$$)$

求对每一个$j$满足条件的最大的$i$的和$。$

解答$:$

因为要满足条件$2$,所以我们必须让$s_{i+1}$$……$$s_j$与$s_1$$……$$s_{j-i}$相同$,$又因为我们想要$i$最大$,$所以就要找到最短的前后公共后缀$,$,这一步需要用一个小$tip$$。$

小$tip$如下$:$ 大家都知道$nxt[len]$是一个字符串的最长前后公共后缀的长度,其实最短也就是一直求$nxt[nxt[len]]$$……$直到值为$0$,这一步自己可以感性理解一下$。$到$0$之前的那个$nxt[len]$即为最短的前后公共后缀$。$

所以到现在这一步$,$我们就可以用$O(n)$的算法$,$算出每次的的$j$$-$最短公共后缀了$。$

求个和就是答案了$。$

撒花花

 

上一篇:Zynq-7000 AP SoC Boot - Multiboot Tech Tip


下一篇:Python语言规范