题意$:$
给定一个字符串$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$$-$最短公共后缀了$。$
求个和就是答案了$。$
撒花花