3723. 字符串查询
作者:
cjx10086
,
2024-03-10 00:57:43
,
所有人可见
,
阅读 31
#include <bits/stdc++.h> // 包含C++标准库中的大部分头文件,用于简化编程
using namespace std; // 使用标准命名空间
const int N = 50010; // 定义字符串的最大长度为50010
string s; // 定义一个字符串变量s,用于存储输入的字符串
int f[26][N]; // 定义一个二维数组f,用于存储前缀和,26表示26个英文字母,N表示字符串的最大长度
int Q; // 定义查询的数量
int a, b, c, d; // 定义查询中的四个整数,分别表示子串的起始和结束位置
int main() {
cin >> s >> Q; // 输入字符串s和查询数量Q
// 初始化前缀和数组的第一列
for (int i = 0; i < s.size(); i++) {
f[s[i] - 'a'][i + 1] = 1; // 对于字符串s中的每个字符,将其对应的前缀和数组位置置为1
}
// 计算前缀和数组的其他列
// 横方向会重复,竖方向不会重复,所以只需要计算[j] 方向的前缀和!!!!!!
for (int i = 0; i < 26; i++) { // 遍历26个英文字母
for (int j = 1; j < N; j++) { // 遍历前缀和数组的每一列
f[i][j] += f[i][j - 1]; // 计算前缀和,即每个位置之前的所有字符的累加和
}
}
// 处理Q个查询
while (Q--) {
scanf("%d%d%d%d", &a, &b, &c, &d); // 输入查询中的四个整数,表示子串的起始和结束位置
bool suc = true; // 假设两个子串的字符分布相同
// 遍历26个英文字母,检查每个字母在两个子串中的数量是否相同
for (int i = 0; i < 26; i++) {
if (f[i][b] - f[i][a - 1] > f[i][d] - f[i][c - 1]) {
// 如果在[a, b)区间内字母i的数量大于在[c, d)区间内字母i的数量,那么suc为false
suc = false;
break; // 如果找到一个字符数量不同,即可断定两个子串字符分布不同,直接跳出循环
}
}
// 输出结果,如果suc为true则输出"DA",否则输出"NE"
cout << (suc ? "DA" : "NE") << endl;
}
return 0; // 程序正常结束
}