题目链接

P10468 兔子与兔子

解题思路

字符串哈希板子题。

思路就是我们给字符串的每一个前缀和后缀都用一种特定的方式使其变为一个值，比如取一个乘数和模数，可以证明这样出错的概率极低。

参考代码

这里使用自然溢出三哈希。

#include<bits/stdc++.h>
using namespace std;
#define map unordered_map
#define forl(i,a,b) for(register long long i=a;i<=b;i++)
#define forr(i,a,b) for(register long long i=a;i>=b;i--)
#define forll(i,a,b,c) for(register long long i=a;i<=b;i+=c)
#define forrr(i,a,b,c) for(register long long i=a;i>=b;i-=c)
#define lc(x) x<<1
#define rc(x) x<<1|1
//#define mid ((l+r)>>1)
#define cin(x) scanf("%lld",&x)
#define cout(x) printf("%lld",x)
#define lowbit(x) (x&-x)
#define pb push_back
#define pf push_front
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define QwQ return 0;
#define ll long long
#define ull unsigned long long
#define lcm(x,y) x/__gcd(x,y)*y
#define Sum(x,y) 1ll*(x+y)*(y-x+1)/2
#define aty cout<<"Yes\n";
#define atn cout<<"No\n";
#define cfy cout<<"YES\n";
#define cfn cout<<"NO\n";
#define xxy cout<<"yes\n";
#define xxn cout<<"no\n";
#define printcf(x) x?cout<<"YES\n":cout<<"NO\n";
#define printat(x) x?cout<<"Yes\n":cout<<"No\n";
#define printxx(x) x?cout<<"yes\n":cout<<"no\n";
ll t;
string s;
ll q,l1,l2,r1,r2;
long long Ss=chrono::steady_clock::now().time_since_epoch().count();
mt19937_64 Apple(Ss);
long long rand_lr(ll l,ll r){
	return Apple()%(r-l+1)+l;
}
ll pw1[1000010],pw2[1000010],pw3[1000010];
ll hash1[1000010],hash2[1000010],hash3[1000010];
ll Base1=779,Base2=223,Base3=667;
ll mod1=1e9+7,mod2=1e9+9,mod3=998244353;
void init()
{
	pw1[0]=pw2[0]=pw3[0]=1;
	forl(i,1,1e6+5)
		pw1[i]=pw1[i-1]*Base1;
	forl(i,1,1e6+5)
		pw2[i]=pw2[i-1]*Base2;
	forl(i,1,1e6+5)
		pw3[i]=pw3[i-1]*Base3;
	forl(i,1,(ll)s.size()-1)
		hash1[i]=(hash1[i-1]*Base1+s[i]);
	forl(i,1,(ll)s.size()-1)
		hash2[i]=(hash2[i-1]*Base2+s[i]);
	forl(i,1,(ll)s.size()-1)
		hash3[i]=(hash3[i-1]*Base3+s[i]);		
}
void solve()
{
	cin>>s>>q;
	s=' '+s;
	init();
	while(q--)
	{
		ll l1,l2,r1,r2;
		cin>>l1>>r1>>l2>>r2;
		printat((hash1[r1]-hash1[l1-1]*pw1[r1-l1+1])==(hash1[r2]-hash1[l2-1]*pw1[r2-l2+1]) &&
				(hash2[r1]-hash2[l1-1]*pw2[r1-l1+1])==(hash2[r2]-hash2[l2-1]*pw2[r2-l2+1]) &&
				(hash3[r1]-hash3[l1-1]*pw3[r1-l1+1])==(hash3[r2]-hash3[l2-1]*pw3[r2-l2+1]) );
	}
}
int main()
{
	IOS;
	t=1;
//	cin>>t;
	while(t--)
		solve();
	QwQ;
}