原题链接:Codeforces961F
题目大意:给定一个字符串 $s$,求 $s$ 所有 $[i,n-i+1]\ (i \in [1, \lceil \frac{n}{2} \rceil])$ 的子串真前缀等于真后缀的最大奇数长度,若无解则为 $-1$。
字符串哈希
解法
约定:为叙述方便,下面所说的前缀和后缀均为真前/后缀。
暴力做法:从小到大枚举 $i$,在求解当前区间 $[i,n-i+1]$ 的时候,从大到小枚举前缀匹配后缀的长度,那么一旦找到一组解,就是最大长度了。然而时间复杂度爆炸。
利用性质:(具体参见参考资料)如果我们已知了 $[(i+1),n-(i+1)+1]$ 这段区间的前缀匹配后缀的最大长度为 $res[i+1]$,那么 $[i,n-i+1]$ 这段区间(上一个区间加上两头)的答案 $res[i] \le res[i+1] + 2$。最好情况是,加上两头仍能匹配成功,那么长度比上一次多 $2$。根据这个性质,我们可以从中间向左边枚举 $i$,在区间内部求解 $[i,n-i+1]$ 区间的答案时,从 $res[i+1]+2$ 开始降序枚举即可。
注意点:题目所求匹配长度必须为奇数,那么我们只要保证最中间的一组求解答案为奇数,那么降序枚举匹配长度时,每次以 $2$ 为步长,即可保证所得到的都是奇数长度了。因此,将 $res[\ ]$ 初始化为 $-1$,并特判 $n$ 为奇数时,中心直接特判 $-1$ 即可。
由于多次哈希被卡那我直接双哈希咯。
代码
|
|