月月查华华的手机
题意 : q个询问 , 问其是否是主串的子序列 ;
题解 : 很显然暴力是O(n^2) 的, 所以需要优化 , 通过观察我们发现 , 子序列中字母的相对位置是不变的，所以可以维护一个数组 next[ i ][ j ], 表示第 i 个位置之后距离其最近的字母 j 所在的位置。由此数组我们便可以提高匹配效率到O(n) ;
维护方法 : 先O(n) 记录字符串中每个字符出现的位置 , 然后再从后往前O(26n) 把每个位置没更新过的字符信息更新一下 ;
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N = 1e6+7; char s[N]; int ne[N][30]; void init() {scanf("%s",s+1);int n = strlen(s+1);for(int i=1;i<=n;i++) ne[i-1][s[i]-'a'] = i;//i-1 位置之后距离其最近的j字符便是其本身了;for(int i=n-1;i>=0;i--)for(int j=0;j<26;j++)if(!ne[i][j]) ne[i][j] = ne[i+1][j];//倒叙传递没更新过的字符信息; } int main() {init();int t;cin>>t;while(t--){char k[N];scanf("%s",k);int m = strlen(k),p=0,flag=1;for(int i=0;i<m;i++){p = ne[p][k[i]-'a'];//建立指针 p=0 迭代在主串中判断某个字符是否出现在位置p后;if(!p){flag=0 ,printf("Non"); //一旦某个字符找不到便break;}}if(flag) printf("Yesn");}return 0; }
123456789101112131415161718192021222324252627282930313233343536373839
