zcmimi's blog

arrow_back后缀数组共12篇文章

avatar
zc
2020-05-16 14:13:00
查看原题

点击跳转

枚举长度L,然后判断长度为L的子串能连续出现几次(1次肯定可以,这里判断出现2次以上的)

复杂度\Theta(\frac n1+\frac n2+\cdots +\frac nn)

假设现在枚举到位置j

找到k=\operatorname{LCP}(suf(j),suf(j+L)),\left \lfloor \frac ki \right \rfloor +1就是从j开始到j之后循环的次数

再判断一下j之前是否有再出现过,就可以得出当前答案

avatar
zc
2020-05-16 14:13:00
查看原题

点击跳转

2/2
Search
search