自动搬运

查看原文

来自洛谷，原作者为

	06ray 再见了，OI

搬运于2025-08-24 22:00:12，当前版本为作者最后更新于2018-12-29 19:32:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题就是让我们判断字符串里的两个字串所包含的每个字母的个数是否相同。

因为子串是连续的，所以我们不难想到前缀和，利用前缀和来快速求出一个子串所包含每个字母的个数。

设 $f[i][j]$为字母$j$在1到$i$的子串出现次数,那么$f[i][j]=f[i-1][j]+(j==c[i]);$

求出前缀和后，求a到b子串出现字符j的次数为 $f[b][j]-f[a][j-1]$

最后判断询问的两个子串所含每个字母的个数是否相同即可。

代码：

#include <iostream>
#include <cstring>
using namespace std;
int f[50100][30];//前缀和数组
int main()
{
	char c[50100];//字符数组
	cin>>c;
	int n=strlen(c);
	for(int i=1; i<=n; i++)//预处理出前缀和
	{
		for(int j=1; j<=26; j++)
		{
			f[i][j]=f[i-1][j];
		}
		f[i][c[i-1]-'a'+1]++;
	}
	int q;
	cin>>q;
	while(q--)
	{
		bool flag=false;
		int a,b,c,d;
		int s[30];
		cin>>a>>b>>c>>d;
		for(int i=1; i<=26; i++)
		{
			if(f[b][i]-f[a-1][i]!=f[d][i]-f[c-1][i])//如果一个字母在这两个子串出现字母不同，就说明这两个子串不符合条件
			{
				flag=1;
				break;
			}
		}
		if(flag)
		{
			cout<<"NE"<<endl;
		}
		else
		{
			cout<<"DA"<<endl;
		}
	}
	return 0;
}