题解：P12422 【MX-X12-T5】「ALFR Round 5」Another string problem

#include<bits/stdc++.h>
#include<bits/extc++.h>
#define ll long long
using namespace std;

ll read(){
    ll x=0,f=1;char ch=getchar_unlocked();
    while(ch<'0'||'9'<ch){if(ch=='-')f=-1;ch=getchar_unlocked();}
    while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar_unlocked();}
    return f*x;
}

const int N = 2e5+5;
int T,n,m,q,nxt[N][30],now[30],k;
char s[N],t[N];
unordered_map<string,bool>mp;

bool dfs(int i,int j,int k,int sum){//printf("%d %d %d\n",i,j,k);
    if(k<=0)return 1;if(i==-1)return 0;if(n-i<k*m-j)return 0;if(sum>=m)return 0;
    return dfs(nxt[i][t[j==m?1:j+1]-'a'],j==m?1:j+1,k-(j==m),sum+nxt[i][t[j==m?1:j+1]-'a']-i-1);
}

void solve(){mp.clear();
    scanf("%s",s+1);n=strlen(s+1);q=read();
    for(int i=0;i<26;i++)now[i]=-1;
    for(int i=n;i>=0;i--){
        for(int j=0;j<26;j++)nxt[i][j]=now[j];
        if(i>0)now[s[i]-'a']=i;
    }while(q--){string sb="";
        scanf("%s",t+1);m=strlen(t+1);k=n/m;
        for(int i=1;i<=m;i++)sb+=t[i];
        if(mp.find(sb)==mp.end()){
            bool flag=dfs(0,0,k,0);puts(flag?"Yes":"No");
            if(flag)mp[sb]=1;else mp[sb]=0;
        }else puts(mp[sb]?"Yes":"No");
    }
}

int main(){
    T=read();while(T--)solve();
    return 0;
}