solution
本来看成了是子段,以为要用ac自动机。
注意到就是要求一个字符串是不是母串的子序列(也就是不要求连续)。这是一个非常经典的问题,我们用表示母串中i这个位置的下一个字符j出现的位置。
如何求这个数组呢?如果,那么。否则。这样就可以很快的求出f数组。
判断一个字符串是不是母串的子序列的时候,直接从0号位置开始,每次跳到原序列中下次出现t[i]的位置即可,如果跳出了母串的最后一个字符,表示不是母串的子序列。
code
/* * @Author: wxyww * @Date: 2020-04-03 06:32:01 * @Last Modified time: 2020-04-03 06:36:08 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; const int N = 1000010; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } int f[N][26],n; char s[N]; void solve() { int p = 0; for(int i = 1;s[i];++i) { p = f[p][s[i] - 'a']; if(p > n) { puts("No");return; } } puts("Yes"); } int main() { scanf("%s",s + 1); n = strlen(s + 1); for(int i = 0;i < 26;++i) f[n][i] = n + 1; for(int i = n - 1;i >= 0;--i) { for(int j = 0;j < 26;++j) f[i][j] = f[i + 1][j]; f[i][s[i + 1] - 'a'] = i + 1; } int m = read(); while(m--) { scanf("%s",s + 1); solve(); } return 0; }