【字符串哈希】Prefixuffix

传送门:CodeVS2585

POI2012


吐槽一下这道题真的是没有结论做不出!

思路:

首先想到模拟,显然GG。

于是就开始撕烤,然而除了暴力枚举并没有思路。

于是查看题解,发现了一条性质:

首先循环相同的2个串可以表示为AB和BA

记$f_i$为|A|为i时|B|的最大值,然后可以发现

$$f_i\geqslant f_{i-1}-2\longrightarrow f_{i-1}\leqslant f_i+2$$

因为两个相同的串两边各去掉一个字符后依然相等。

这个结论很好证,然而根本想不到。

然后i从$\frac{n}{2}$开始往下枚举,然后j记录当前的$f_i$,那么j的取值范围就收到$f_i$的限制,然后加(两)个哈希判一下就好了。

然后就可以秒了。


贴代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long
#define Mo (LL)1000000009
#define BASE (LL)233233
#define min(x,y) ((x)<(y)?(x):(y))
LL Hash[1000030],hAsh[1000030],pw[1000030];
LL ans,n;
char s[1000030];
LL get_hash(LL x,LL y){return (hAsh[y]-(hAsh[x-1]*pw[y-x+1])%Mo+Mo)%Mo;}
int main(){
scanf("%lld\n",&n);
for (int i=1;i<=n;i++) s[i]=getchar();
pw[0]=1;
for (int i=1;i<=n;i++){
Hash[i]=(Hash[i-1]+s[i])%Mo;
hAsh[i]=(hAsh[i-1]*BASE+s[i])%Mo;
pw[i]=pw[i-1]*BASE%Mo;
}
for (int i=n/2,j=0;i>0;i--,j=min(j+2,(n/2-i))){
for (;j>0;j--)
if (get_hash(i+1,i+j)==get_hash(n-i-j+1,n-i) && Hash[i+j]-Hash[i]==Hash[n-i]-Hash[n-i-j])
break;
if (get_hash(1,i)==get_hash(n-i+1,n) && Hash[i]==Hash[n]-Hash[n-i])
if (ans<i+j) ans=i+j;
}
printf("%lld\n",ans);
return 0;
}