AcWing 3723. 字符串查询
原题链接
简单
#include <vector>
#include <iostream>
using namespace std;
class Wrapper {
private:
int data[26];
public:
Wrapper() {}
void add(char ch) {
data[ch - 'a']++;
}
void remove(char ch) {
data[ch - 'a']--;
}
bool operator== (Wrapper& other) {
for (auto i = 0; i < 26; ++i) {
if (other.data[i] != data[i]) {
return false;
}
}
return true;
}
static Wrapper gap(Wrapper& greater, Wrapper& smaller) {
Wrapper wp;
for (auto i = 0; i < 26; ++i) {
wp.data[i] = greater.data[i] - smaller.data[i];
}
return wp;
}
void print() {
for (int i = 0; i < 26; ++i) {
if (data[i] != 0) {
cout << "{ " << (char)('a' + i) << " " << data[i] << " }";
}
}
cout << endl;
}
};
vector<Wrapper> prex;
void init(string& s) {
prex = vector<Wrapper>(s.size(), Wrapper());
Wrapper cur;
cur.add(s[0]);
prex[0] = cur;
for (auto i = 1; (size_t)i < s.size(); ++i) {
cur.add(s[i]);
prex[i] = cur;
}
}
void handle(string& s, vector<int>& d) {
Wrapper begin1 = prex.at(d[0]);
Wrapper end1 = prex.at(d[1]);
Wrapper begin2 = prex.at(d[2]);
Wrapper end2 = prex.at(d[3]);
// t1
Wrapper gap1 = Wrapper::gap(end1, begin1);
Wrapper gap2 = Wrapper::gap(end2, begin2);
gap1.add(s[d[0]]);
gap2.add(s[d[2]]);
// gap1.print();
if (gap1 == gap2) {
cout << "DA" << endl;
} else {
cout << "NE" << endl;
}
}
int main(int,char**) {
string line;
cin >> line;
int q;
cin >> q;
vector<vector<int>> input;
for (auto i = 0; i < q; ++i) {
vector<int> tmp;
for (auto j = 0; j < 4; ++j) {
int n ;
cin >> n;
tmp.push_back(n - 1);
}
input.push_back(std::move(tmp));
}
init(line);
for (auto& v : input) {
handle(line, v);
}
}