1.暴力 10/12
#include <bits/stdc++.h> using namespace std; int n; string a[10005]; int main() { cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; string ll; cin >> ll; for (int i = 0; i < n; i++) { string u = a[i]; int num = 0; int j = 0; for (int k = 0; k < ll.size(); k++) { if (ll[k] == a[i][j]) { num++; j++; } } if (num == a[i].size()) { cout << "YES" << endl; } else cout << "NO" << endl; } }
2.记录每个字母（共26个）的位置下标，并分别存在各自的字母下标数组中（例：a数组:1 3 5;b数组:2 6）
找一个字母的位置，即在此字母的下标数组中找（靠近左边的）&&（>前一个字母下标的数字）
(即若单词为bab，则先找b数组中最左侧位置2，再找a数组中>2&&最左侧的数字3，再找b数组中>3&&最左侧的数字6。如果都能找到位置，则说明此单词在歌词中)
#include <bits/stdc++.h> using namespace std; const int N = 1e4 + 10; int n, l, r, mid, ans; string a[N], ll; vector<int> abc[27]; // 字母下标数组 int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; string ll; cin >> ll; for (int i = 0; i < ll.size(); i++) abc[ll[i] - 'a'].push_back(i); // 在各字母表中记录位置下标 for (int i = 1; i <= n; i++) { int len = a[i].size(), now = -1; // now记录此时字母的位置应在now右侧 int flag = 1; for (int j = 0; j < len; j++) { l = 0, r = abc[a[i][j] - 'a'].size() - 1, ans = -1; // 二分字母下标数组。找字母下标 while (l <= r) { mid = (l + r) / 2; if (abc[a[i][j] - 'a'][mid] > now) { r = mid - 1, ans = mid; } else l = mid + 1; } if (ans == -1)//不能找到一个位置使此单词的某一字母在歌词中 { flag = 0; break; } now = abc[a[i][j] - 'a'][ans];//now更新为此字母当前位置，下一字母的位置应在now之后 } if (flag) { cout << "YES" << endl; } else cout << "NO" << endl; } }
