#include<bits/stdc++.h> using namespace std; int arr[int(1e6+5)],pc[int(int(1e6+5))]; int main(){ string s; cin>>s; int len=s.size(),n; int p=131; arr[0]=1;pc[0]=1; for(int i=1;i<=len;i++){ arr[i]=arr[i-1]*p+(s[i-1]-'a'); pc[i]=pc[i-1]*p; } cin>>n; for(int i=0;i<n;i++){ int l1,r1,l2,r2; cin>>l1>>r1>>l2>>r2; int num1=arr[r1]-arr[l1-1]*pc[r1-l1+1]; int num2=arr[r2]-arr[l2-1]*pc[r2-l2+1]; if(num1==num2){ cout<<"Yes\n"; } else cout<<"No\n"; } return 0; }

帮忙整理一下格式谢谢。

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
ull h[1000010];
ull c26[1000010];

int main(){
	string x;
	cin>>x;
	int m;
	cin>>m;
	ull sz=x.size();
    c26[0]=1;
	for(int i=1;i<=sz;i++){
		h[i]=h[i-1]*1000000001201+(ull)(x[i-1]-'a');
        c26[i]=c26[i-1]*1000000001201;
	}
	
	while(m--){
		int l1,l2,r1,r2;
		cin>>l1>>r1>>l2>>r2;
		ull h1,h2;
		h1=h2=0;
		h1=h[r1]-h[l1-1]*c26[r1-l1+1];
		h2=h[r2]-h[l2-1]*c26[r2-l2+1];
		if(h1==h2)cout<<"Yes\n";
		else cout<<"No\n";
	} 
}

(肯定没人发现语言是c++不是cpp)

#include <bits/stdc++.h>
using namespace std;
unsigned long long int h[1000005],p[1000005];
int l1,l2,r1,r2;
string s;
int m;
int main() 
{
	cin >> s;
	p[0] = 1;
	for (int i = 1;i <= s.length();i++)
	{
		p[i] = p[i - 1] * 131; 
		h[i] = h[i - 1] * 131 + (s[i - 1] - '0'); 
	}
	cin >> m;
	while (m--)
	{
		cin >> l1 >> r1 >> l2 >> r2;
		if (h[r1] - h[l1 - 1] * p[r1 - l1 + 1] == h[r2] - h[l2 - 1] * p[r2 - l2 + 1])
		{
			cout << "Yes\n";
		}
		else
		{
			cout << "No\n";
		}
	}
	return 0;
}

题意

字符串哈希，比较子串。

思路

字符串哈希，比较子串。

首先，是个hand someboy都知道秦九韶算法吧？（bushi）

比如说我的aabbaabb，我们把它抽象（玩点抽象怎么你了）成11221122，然后设p（进制）为10（方便理解，这题偶数会被卡），那么想让它s[1]=1，s[2]=11，s[3]=112……那就直接进化：s[i]=s[i-1]*p+a[i]。

a[i]就是你把它抽象成的东西……

然后求s[l,r]我们就可以末项减首项求前缀和，看我推公式：

$s_{l,r}=s_r-s_{l-1}*p^{r-l+1}$

只所以要乘，相当于123与1之间隔23需要$123-1*10^2$，也就是补位。

代码

#include<iostream>
#define P 13//前女友2013年的…… 
#define N int(2e6)
#define S(l,r) (s[r]-s[l-1]*p[r-l+1])
using namespace std;
unsigned long long s[N]{};
unsigned long long p[N]{1};
//自然溢出就不需要mod了
//就是要开unsigned 
int main(){
	string a("");//避嫌（bushi）
	//前缀和数组要用s
	//原版代码我是把前缀和叫a的，都是为了给你们讲
	cin>>a;
	int n(a.size());//长度 
	a='X'+a;//垫着，前女友姓氏首字母是X…… 
	for(int i(1);i<=n;i++){
		p[i]=p[i-1]*P;
		s[i]=s[i-1]*P+a[i]-'a'+1;
	}
	int m(0);
	cin>>m;
	while(m--){
		int l1(0);
		int r1(0);
		int l2(0);
		int r2(0);
		cin>>l1>>r1>>l2>>r2;
		if(S(l1,r1)==S(l2,r2))
			cout<<"Yes\n";
		else
			cout<<"No\n";
	}
	return 0;
}