题目:
样例:
题目链接:
月月查华华的手机
#析题得侃:
Code:
#include <vector> #include <cstdio> #include <string> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn = 1e6 + 10; string a,b; int n; vector<int>ve[maxn]; int main(void) { cin >> a; for(int i = 0; i < a.size(); i ++) { // 存储每个模式串中每个字符的位置 ve[a[i] - 'a'].push_back(i); } scanf("%d",&n); while(n --) { cin >> b; bool vis = true; int pos = -1; // 记录目前可以到达的最大位置 for(int i = 0; i < b.size(); i ++) { // 说明模式串中没有该字符 if(ve[b[i] - 'a'].size() == 0) { vis = false; break; } int p = b[i] - 'a'; int l = 0,r = ve[p].size() - 1; // 模式串中的位置已经无法满足要求 if(pos >= ve[p][r]) { vis = false; break; } while(l < r) { // 二分查找第一个 > pos 的位置 int mid = l + r >> 1; if(ve[p][mid] > pos) r = mid; else l = mid + 1; } pos = ve[p][r]; } if(vis) cout << "Yes" << endl; else cout << "No" << endl; } return 0; }
后记:
如有解释的不清的地方,欢迎提出来,共同交流,共同学习进步。
欢迎各位大佬参观我的博客,提出不足,本人会虚心改正,在此万分感谢。
https://www.cnblogs.com/prjruckyone/