[ABC284F] ABCBAC
阅读原文时间:2023年08月22日阅读:2

2023-01-09

题目传送门

翻译

难度&重要性(1~10):2.5

题目来源

AtCoder

Z函数,KMP,字符串Hash

对于一个 \(f_S\),我们可以将它化成三个部分。

也就是 \([0,i-1],[i,i+n-1],[i+n,2n]\)。

我们可以不断枚举中断点 ii,判断中间子串是否是原字符串的回文串,时间复杂度 \(O(n^2)\)。

我们不得不寻找一种更好的方法,对此我们可以把它切成四部分。

即 \([0,i-1],[i,n],[n+1,i+n-1],[i+n,2n]\)。

仅当 \(T\) 是合法的字符串,有 \(i\) 满足 \([0,i-1]\) 和 \([n+1,i+n-1],[i,n]\) 和 \([i+n,2n]\) 互为回文数。

为了运算方便,我们可以把 \([n+1,2n]\) 翻转过来。

显然的,\([0,n]\) 绝对是 \([n+1,2n]\) 右移复制后的子串。

我们只要找到 \([0,n]\) 在 \([n+1,2n][n+1,2n]\) 串中的位置,逆推之后,我们就能确定 \(i\) 的位置,这道题就做完了。

已完成

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器