一开始以为是kmp,结果发现是子序列,不要求连续。
题意:
给出一个字符串s,接着给m个询问,每次询问一个字符串p,问p是否是s的子序列。
len(s)<=10^6,m<=10^6,∑p<=10^6.
思路:
一开始想的是,预处理出s中的每个字母依次出现的位置,在询问的时候维护当前已经到达的位置pos,然后找出第一个大于pos的字母p[i]的位置。结果超时了。
后来考虑到可能对每个字母查找位置的时候有点浪费时间,于是改成了二分查找,结果还是超。。
无奈,看了一下题解。
用nxt[i]['a'-'z']表示第i个位置后面第一次出现某个字母的位置。
这里我们可以维护一个la[j]数组表示字母j的最左侧位置。因此我们可以从后往前扫描字符串s,然后预处理出nxt数组。
在每次询问的时候,我们直接维护当前位置now,然后直接利用nxt[now][p[i]]跳就可以了。
复杂度主要是在预处理中,为O(26*10^6)
代码:
#include<bits/stdc++.h> using namespace std; string s; int nxt[1000050][26],la[26]; int main() { cin>>s; for(int i=s.size()-1;i>=0;i--){ int tmp=s[i]-'a'; for(int j=0;j<26;j++)nxt[i+1][j]=la[j]; la[tmp]=i+1; } for(int j=0;j<26;j++)nxt[0][j]=la[j]; int m; cin>>m; string p; while(m--){ cin>>p; int now=0; bool flag=true; for(int i=0;i<p.size();i++){ if(nxt[now][p[i]-'a'])now=nxt[now][p[i]-'a']; else { flag=false; break; } } if(flag)cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }