AtCoder Beginner Contest 284-F - ABCBAC(双哈希)

F - ABCBAC

题目大意：

给定一个正整数n，和一个长度为2*n的字符串s
问s串能不能是由一个t串经过如下操作变成s串：

1. t串的前i个字符
2. t串的反转串
3. t串的后(n-i)个字符

如果存在这样的t串，请输出t串和i，否则输出-1

解题思路：

双哈希匹配字符串，只需要线性的扫描s串的前n个字符，按照操作匹配即可

双哈希：

存两套base和mod，用pair<int,int>来存储，保证了发生冲突的可能性更低
板子：

#include<bits/stdc++.h>
using namespace std;
# define int long long
# define endl "\n"
# define mk(a,b) make_pair(a,b)
# define fi first
# define se second
const int N = 2010000, inf = 0x3f3f3f3f;

typedef pair<int,int> hashv;
const int mod1 = 1e9+7;
const int mod2 = 1e9+9;

hashv operator + (hashv a,hashv b){
	int c1 = a.fi+b.fi,c2 = a.se+b.se;
	if(c1>=mod1) c1 -= mod1;
	if(c2>=mod2) c2 -= mod2;
	return mk(c1,c2);
}

hashv operator - (hashv a,hashv b){
	int c1 = a.fi-b.fi,c2 = a.se-b.se;
	if(c1<0) c1 += mod1;
	if(c2<0) c2 += mod2;
	return mk(c1,c2);
}

hashv operator * (hashv a,hashv b){
	return mk(1ll*a.fi*b.fi%mod1,1ll*a.se*b.se%mod2);
}
hashv pw[N],s[N];
char tt[N];
void solve() {
	int n;
	cin>>n;
	cin>>(tt+1);
	hashv base = mk(13331,23333);
	pw[0] = mk(1,1);
	for(int i = 1;i <= n;++i){
		pw[i] = pw[i-1]*base;
		s[i] = s[i-1]*base+mk(tt[i],tt[i]);
	}

代码实现：

#include<bits/stdc++.h>
using namespace std;
# define int long long
# define endl "\n"
# define mk(a,b) make_pair(a,b)
# define fi first
# define se second
const int N = 2010000, inf = 0x3f3f3f3f;

typedef pair<int,int> hashv;
const int mod1 = 1e9+7;
const int mod2 = 1e9+9;

hashv operator + (hashv a,hashv b){
	int c1 = a.fi+b.fi,c2 = a.se+b.se;
	if(c1>=mod1) c1 -= mod1;
	if(c2>=mod2) c2 -= mod2;
	return mk(c1,c2);
}

hashv operator - (hashv a,hashv b){
	int c1 = a.fi-b.fi,c2 = a.se-b.se;
	if(c1<0) c1 += mod1;
	if(c2<0) c2 += mod2;
	return mk(c1,c2);
}

hashv operator * (hashv a,hashv b){
	return mk(1ll*a.fi*b.fi%mod1,1ll*a.se*b.se%mod2);
}

hashv pw[N],s[N],t[N];
char tt[N];
void solve() {
	int n;
	cin>>n;
	n = n*2;
	cin>>(tt+1);
	hashv base = mk(13331,23333);
	pw[0] = mk(1,1);
	for(int i = 1;i <= n;++i){
		pw[i] = pw[i-1]*base;
		s[i] = s[i-1]*base+mk(tt[i],tt[i]);
	}
	for(int i = n;i>=1;--i){
		t[i] = t[i+1]*base+mk(tt[i],tt[i]);
	}
	
	for(int i = 0;i<=n/2;++i){
		/*s1取前i个和后(n-i)个*/
		hashv s1 = s[i]*pw[n/2-i]+(s[n]-s[i+n/2]*pw[n/2-i]);
		/*s2取从i+1开始的n个*/ 
		hashv s2 = t[i+1]-t[i+1+n/2]*pw[n/2];
		//相同则输出 
		if(s1 == s2){
			for(int j = n/2-1;j>=0;--j){
				printf("%c",tt[i+1+j]);
			}
			puts("");
			printf("%lld\n",i);
			return;
		}
	}
	puts("-1");

}
int __;
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	__ = 1;
//	cin >> __;
	while (__--) solve();


	return 0;
}