【字符串哈希】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;
}