本文主要是介绍3723. 字符串查询：做题笔记，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
思路
代码
注意点
3723. 字符串查询
思路
这道题感觉和常见的前缀和问题不太一样，前缀和的另一种应用：可以统计次数。
这道题我们想判断一个单词的其中一段子序列A是否可以通过重新排列得到另一段子序列B。
我看到这道题的时候想着可能要判断这一段中存在的元素是否在相比较的序列中存在，额可能要用到二分查找？等等，挺麻烦的。而且这样没有考虑到如果存在两个相同的字母，好像并没有想到处理这种情况。
所以大体的思路应该是：我们判断A序列中是否存在某个字母且其个数是否和B序列中完全符合。
那么前缀和在这里的作用就是按照字母统计出：该单词中每个字母在每个前缀中的个数。
也就是我们之前前缀和的对象都是数字，这里我们的操作对象是字母。
一共有26个字母，因此要分别计算出这26个字母对应的前缀和，比较好的处理方式就是创建一个二维数组，行数直接为26。利用列来表示每个字母对应的前缀和。
(我们这里主要利用二维数组来方便表示含义，不需要联想到实际的二维数组。记得之前在tire字符串统计算法里我们就是这样利用二维数组的，原来这样利用二维数组含义方便表示还怪常见哩hh)
由于要计算26轮前缀和，因此我们的循环最外层就是控制计算26轮的，且其指针刚好也可以代表着字母顺序，内部循环就是我们正常的前缀和步骤：遍历这个单词，如果遍历到的字母是我们目前正在统计的字母的前缀和，那么就利用前缀和计算公式q[i]=q[i-1]+a[i]，由于这里我们只是统计次数，a[i]只有两种可能0/1，因此不需要多创建，直接用if语句实现即可。
(注意如何判断遍历到的字母是我们目前正在统计的字母？就是将当前字母 -a字符 得到的就是该字母在第几位，也就是我们最外层循环此时的轮数。[我们将字母用从0-25的数字来表示了])
统计出前缀和之后就是判断两段子序列中字母是否匹配了。
我们输入的abcd就是前缀和的某两个区间。我们遍历这两个区间的26个字母是否个数都相同，只要出现一个不同的就不符合题意。
代码
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N=1e5+10;
int s[26][N];
char str[N];
signed main()
{/*ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);*/scanf("%s",str+1);//前缀和从下标为1开始for(int i=0;i<26;i++){for(int j=1;str[j];j++){if(str[j]-'a'==i)s[i][j]=s[i][j-1]+1;else s[i][j]=s[i][j-1];}}int q;cin>>q;while(q--){int a,b,c,d;cin>>a>>b>>c>>d;bool st=1;for(int i=0;i<26;i++){if(s[i][b]-s[i][a-1]!=s[i][d]-s[i][c-1]){st=0;break;}}if(st)puts("DA");else puts("NE"); }return 0;
}注意点
①
注意我们这里由于输入的是字符串，但是我们想利用前缀和，我们希望输入的时候从字符串的第二位也就是下标为1的位置开始存储，所以我们使用scanf输入，采用这样的形式
scanf("%s",str+1);
来实现。
那么我们使用了scanf，就不能再写对于cin/cout的提速的内容了。下面是解释：
②
习惯一下用puts实现输出内容。
③
这里想再记一下做另一道题的时候我用了sort函数，但没用对。在这里补充一下关于sort函数。
sort(begin, end)：对数组或容器中的元素进行排序。begin 是指向待排序区间第一个元素的指针或迭代器，end 是指向待排序区间最后一个元素的下一个位置的指针或迭代器。
注意这个函数的参数类型。
如果想对一个，下标从0开始有n+1个元素的b[]数组进行排序：
sort(b,b+n);不要这样写：sort(b[1],b[n])
如果我们创建的是vector类型的数组，对其元素进行排序，那么调用sort函数就需要用.begin(),.end()的参数写法
sort(myVector.begin(), myVector.end());好啦写到这。(突然发现写文章里可以上传视频hh之前都是插链接😂)
有问题欢迎指出，一起加油！！！！
这篇关于3723. 字符串查询：做题笔记的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
