OI字符串问题 - 遗忘了他的世界，deque
请教字符串的操作题目：E. 遗忘了它的世界
题目背景
世界正在遗忘它，遗忘它的名字，遗忘它的事迹，遗忘它的足迹，只有你还记得它的名字。
题目描述
一切关于他的事情都被遗忘了，哪怕只是一个小小的字符串。
我们给出$n$和它的名字，表示有$n$个待遗忘字符串。
对于每个待遗忘字符串 $a$ 与它的名字$n$我们将在$a$中所有存在于$n$的字符进行删除操作，处理后的字符串就是遗忘后的字符串。
如果$a$的每个字符都能在$n$中找到位置不重复且$ ASCII $值相等的字符(即 $ch$字符在$n$中出现多少次，在$a$中至少出现同样的次数)。我们称$n$为“遗忘字符串”。
(如 $b$ 为 $abb$，$a1 $为$ baa$，$a2 $为 $bbab$，$a2$是“遗忘字符串”，而 $a1$ 不是)。
输出所有遗忘后的字符串。
对于“遗忘字符串”，我们分别输出遗忘前的字符串与遗忘后的字符串。
如果待遗忘字符串与它的名字相等，输出$equal$.
输入格式
第一行输入$l$代表数据总组数。
对于每组数据：
首先输入字符串总数$a$和他的名字。
然后输入$a$行，每行一个字符串。
输出格式
首先输出$n$行，每行对应一个遗忘的字符串。
如果遗忘的字符串为空串，那么输出一个空行。
然后，对于每个“遗忘字符串”，输出两行。
第一行为 $past：$遗忘前的字符串
第二行为 $now：$遗忘后的字符串或$equal$
样例
样例输入
2
2 zyx
fxl
itzex
4 fxl
iamfxl
ixpxi
ifxli
fxl
样例输出
fl
ite
iam
ipi
ii
past:iamfxl
now:iam
past:ifxli
now:ii
past:fxl
now:equal
数据范围
我的思路
check函数判断、去重；创建deque存储名字和待遗忘字符串，排序后依次pop_front()，然后判断剩下的front哪个大，判别它是不是遗忘字符串。最后输出。
我的代码
#include strs;
deque <char> exc, qname;
string name, tmp, ans;
int n, data;
char nextc;
inline void check(string str, string nam) {
except.clear();
pair <int, int> let[27];
bool flag = false;
int tmp = 0;
for (int i = 0; i < nam.length(); ++i) {
for (int j = 0; j < str.length(); ++j)
if (name[i] == str[j])
except.push_back(str[j]);
}
for (int i = 0; i < except.size(); ++i) {
if (except[i] == nextc)
except[i] = 127;
else
nextc = except[i];
}
sort(except.begin(), except.end());
sort(nam.begin(), nam.end());
for (int i = 0; i < except.size(); ++i) exc.push_back(except[i]);
for (int i = 0; i < nam.size(); ++i) qname.push_back(nam[i]);
while (!qname.empty() && !exc.empty()) {
while (qname.empty() || exc.empty() ? false : qname.front() == exc.front()) {
qname.pop_front();
exc.pop_front();
++tmp;
}
if (qname.empty() || exc.empty() ? false : qname.front() >= exc.front())
flag = true;
else
flag = false;
}
if (flag) {
cout << "past:" << str << "\nnow:";
for (int i = 0; i < str.length(); ++i) {
for (int j = 0; j < name.length(); ++j) {
if (str[i] == name[j])
goto nrsame;
}
cout << str[i];
nrsame:;
}
}
else {
for (int i = 0; i < str.length(); ++i) {
for (int j = 0; j < name.length(); ++j) {
if (str[i] == name[j])
goto rsame;
}
cout << str[i];
rsame:;
}
}
cout << '\n';
return;
}
int main(int argc, char* argv[]) {
ios::sync_with_stdio(false);
cin >> ::data;
for (int iakioi = 0; iakioi < ::data; ++iakioi) {
strs.clear();
cin >> n >> name;
for (int i = 0; i < n; ++i) {
getline(cin, tmp, '\n');
strs.push_back(tmp);
if (tmp == name)
cout << "past:" << tmp << "\nnow:equal\n";
else if (tmp.length() == 1)
cout << '\n';
else
check(tmp, name);
}
}
system("pause");
return 0;
}
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
vector<string> forget(vector<string>& strs, const string& name) {
unordered_map<char, int> name_chars;
for (char c : name) {
name_chars[c]++;
}
vector<string> results;
for (const string& s : strs) {
unordered_map<char, int> s_chars;
for (char c : s) {
s_chars[c]++;
}
bool is_forgotten = true;
string forgotten_s;
for (char c : s) {
if (name_chars.count(c) && s_chars[c] >= name_chars[c]) {
s_chars[c] -= name_chars[c];
} else {
is_forgotten = false;
forgotten_s += c;
}
}
if (is_forgotten) {
results.push_back(forgotten_s);
} else {
results.push_back("");
}
cout << "past:" << s << endl;
if (is_forgotten) {
cout << "now:" << forgotten_s << endl;
} else if (s == name) {
cout << "now:equal" << endl;
} else {
cout << "now:" << s << endl;
}
}
return results;
}
int main() {
int t;
cin >> t;
while (t--) {
int n;
string name;
cin >> n >> name;
vector<string> strs(n);
for (int i = 0; i < n; i++) {
cin >> strs[i];
}
forget(strs, name);
if (t > 0) {
cout << endl;
}
}
return 0;
}
其思路如下：
对于每一个字符串 $s$，用一个哈希表 $s_chars$ 统计其中每个字符的出现次数。
再用一个哈希表 $name_chars$ 统计遗忘字符串 $name$ 中每个字符的出现次数。
对于 $s$ 中的每个字符 $c$，如果 $c$ 在 $name$ 中出现且 $s_chars[c] \geq name_chars[c]$，则说明 $c$ 在 $s$ 中出现次数不少于在 $name$ 中出现的次数，可以进行遗忘操作；否则说明 $c$ 不能被遗忘，此时将它追加到遗忘前的字符串 $forgotten_s$ 中。
如果 $s$ 的每个字符都能被遗忘，那么遗忘后的字符串就是 $forgotten_s$；否则 $s$ 不能被遗忘，遗忘后的字符串就是 $s$ 本身（如果 $s$ 与 $name$ 相等，则遗忘后的字符串为“equal”）。
最后输出所有的遗忘后的字符串。