月月查华华的手机【牛客tracker 每日一题】

月月查华华的手机

时间限制：2秒 空间限制：256M

知识点：思维题

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

月月和华华一起去吃饭了。期间华华有事出去了一会儿，没有带手机。月月出于人类最单纯的好奇心，打开了华华的手机。哇，她看到了一片的Q Q QQQQ推荐好友，似乎华华还没有浏览过。月月顿时醋意大发，出于对好朋友的关心，为了避免华华浪费太多时间和其他网友聊天，她要删掉一些推荐好友。但是为了不让华华发现，产生猜疑，破坏了他们的友情，月月决定只删华华有可能搭讪的推荐好友。
月月熟知华华搭讪的规则。华华想与某个小姐姐搭讪，当且仅当小姐姐的昵称是他的昵称的子序列。为了方便，华华和小姐姐的昵称只由小写字母构成。为了更加方便，保证小姐姐的昵称长度不会比华华的长。
现在月月要快速的判断出哪些推荐好友要删掉，因为华华快回来了，时间紧迫，月月有点手忙脚乱，所以你赶紧写个程序帮帮她吧！

输入描述：

第一行输入一个字符串A AA表示华华的昵称。
第二行输入一个正整数N NN表示华华的推荐好友的个数。

接下来N NN行，每行输入一个字符串B i B_iBi​表示某个推荐好友的昵称。

1 ≤ ∣ A ∣ ≤ 1 0 6 ， 1 ≤ N ≤ 2 × 1 0 5 ， 1 ≤ ∑ i = 1 N B i ≤ 1 0 6 1≤∣A∣≤10^6，1≤N≤2×10^5，1≤∑_{i=1}^NB_i≤10^61≤∣A∣≤106，1≤N≤2×105，1≤∑i=1N​Bi​≤106

输出描述：

输出N NN行，对于第i ii个推荐好友，如果华华可能向她搭讪，输出Y e s YesYes，否则输出N o NoNo。
注意大写，同时也要注意输出效率对算法效率的影响。

示例1

输入：

noiauwfaurainairtqltqlmomomo 8 rain air tql ntt xiaobai oiiiooo orzcnzcnznb ooooo

输出：

Yes Yes Yes Yes No Yes No No

备注：

本题已于下方时间节点更新，请注意题解时效性：

1. 2025 − 12 − 15 2025-12-152025−12−15n nn的数据范围从1 0 6 10^6106缩减至2 × 1 0 5 2×10^52×105，同时增加了若干组数据。

解题思路

首先预处理华华的昵称字符串A AA，构建一个二维数组s ss（大小为(l e n ( A ) + 1 ) × 26 len(A)+1)×26len(A)+1)×26），从后往前遍历A AA，记录每个位置i ii处26 2626个小写字母在i ii及之后第一次出现的索引（初始时最后一个位置的所有字母索引设为− 1 -1−1）；随后处理每个好友的昵称字符串B BB，用指针p o s pospos跟踪A AA中当前匹配的位置，逐个遍历B BB的字符，查找该字符在A AA中p o s pospos位置之后的首次出现索引，若不存在则判定B BB不是A AA的子序列（输出N o NoNo），若存在则更新p o s pospos为该索引+ 1 +1+1，遍历完成则判定为子序列（输出Y e s YesYes）；该方法预处理时间复杂度为O ( l e n ( A ) × 26 ) O(len(A)×26)O(len(A)×26)，单次查询为O ( l e n ( B ) ) O(len(B))O(len(B))，适配l e n ( A ) len(A)len(A)和所有B BB的长度和达1 e 6 1e61e6、N NN达2 e 5 2e52e5的规模，通过预处理避免重复查找，高效完成子序列判断。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=1e5+10;constll M=26;intmain(){string x;cin>>x;ll n=x.size();vector<array<ll,M>>s(n+1);for(ll c=0;c<M;c++)s[n][c]=-1;for(ll i=n-1;i>=0;i--){s[i]=s[i+1];s[i][x[i]-'a']=i;}ll t;cin>>t;while(t--){string y;cin>>y;ll pos=0;boolok=1;for(charc:y){ll idx=c-'a';if(pos>n||s[pos][idx]==-1){ok=0;break;}pos=s[pos][idx]+1;}cout<<(ok?"Yes\n":"No\n");}return0;}