给一个大写字符串 \(S_{txt}\) ，每次操作可以删除一个字符 \(C\) ，且只能删除 \(S_{txt}\) 中的第一个字符 \(C\) 。给一个字符串 \(S_{pat}\) ，询问 \(S_{pat}\) 能否由 \(S_{txt}\) 经过若干次字符删除后得到。
逆向：“删除第一个字符 \(C\) ”的逆向为，“在第一个字符 \(C\) 左边任意位置增加一个字符 \(C\) ”。即 \(S_{txt}\) 可视为 \(S_{pat}\) 增加字符得到。
- 于是，对于 \(S_{pat}\) 中的任意字符 \(C\) ，若 \(C\) 是 \(S_{pat}\) 右起第 \(x\) 个 \(C\) ，则也会是 \(S_{txt}\) 右起第 \(x\) 个 \(C\) 。
故只需要使用一个指针 \(i\) 从右到左扫 \(S_{pat}\) ，同时使用指针 \(l\) 从右往左找 \(S_{pat_{i}}\) 的匹配字符。判断 \(S_{pat}\) 是 \(S_{txt}\) 的子序列，且满足上述限制即可从 \(S_{txt}\) 删除字符得到 \(S_{pat}\) 。
只需判断 \(S_{txt}\) 有 \(S_{txt}.length\) 个字符满足限制。
view
#include <bits/stdc++.h>
void solve() {
std::string s_txt, s_pat; std::cin >> s_txt >> s_pat;
int n = s_txt.length(), m = s_pat.length();
int l = n - 1, ok = 0;
int cnt_txt[26] = {0};
int cnt_pat[26] = {0};
for (int i = m - 1; ~i; --i, --l) {
cnt_pat[s_pat[i] - 'A']++;
while (l >= 0 && s_txt[l] != s_pat[i]) {
cnt_txt[s_txt[l] - 'A']++;
l--;
}
if (l < 0) break;
cnt_txt[s_txt[l] - 'A']++;
ok += (cnt_pat[s_pat[i] - 'A'] == cnt_txt[s_txt[l] - 'A']);
}
std::cout << (ok == m ? "YES" : "NO") << '\n';
}
signed main() {
int _ = 1; std::cin >> _;
while (_--) solve();
return 0;
}