思路和验题人的题解一样。

P12422

solution

/*
compute hash;
pos = -1;
while(cnt < t.len)
{
    for(int s = 1 << (logmaxn + 1);s;s >>= 1)
        if(gethash(pos + 1 , pos + s * t.len) == gethash())
            pos += (s * t.len);
    if(pos == len - 1){flag = true;break;}
    cnt++;
}
gethash(l , r) = ((hash[r] - hash[l - 1] * powmod[r - l + 1]) % modn + modn) % modn
*/
#include <bits/stdc++.h>
using namespace std;

#define maxn 200005
#define maxs 262144 //1 << 18
#define logmaxs 18
#define hashnum 2
int csyy , quenum;
char par[maxn + 1] , que[maxn + 1];int plen , qlen;
long long parhash[hashnum][maxn + 1] , quehash[hashnum][logmaxs + 1];
long long powmod[hashnum][maxn + 1];int ind;//26 ^ i
long long hashmod[hashnum] = {998244353 , 10000007};
int getlen(char *s)
{
    int res = 0;
    for(char *p = s;*p != '\0';p++ , res++);
    return res;
}
int main()
{
    scanf("%d" , &csyy);
    for(int i = 0;i < hashnum;i++)powmod[i][0] = 1;
    ind = 1;
    while(csyy--)
    {
        scanf("%s%d" , par , &quenum);
        plen = getlen(par);
        for(;ind <= plen;ind++)
            for(int i = 0;i < hashnum;i++)
            {
                // if(ind >= maxn + 1){puts("a");return 0;}
                powmod[i][ind] = (powmod[i][ind - 1] * 26) % hashmod[i];
            }
        for(int modi = 0;modi < hashnum;modi++)
        {
            parhash[modi][0] = par[0] - 'a';
            for(int i = 1;i < plen;i++)
                parhash[modi][i] = (parhash[modi][i - 1] * 26 + 1LL * (par[i] - 'a')) % hashmod[modi];
        }
        // printf("par\t\t");
        // for(int i = 0;i < plen;i++)
        //     printf("%lld " , parhash[0][i]);
        // puts("");
        while(quenum--)
        {
            scanf("%s" , que);
            qlen = getlen(que);
            for(int modi = 0;modi < hashnum;modi++)
            {
                quehash[modi][0] = 0;
                for(int i = 0;i < qlen;i++)
                    quehash[modi][0] = (quehash[modi][0] * 26 + 1LL * (que[i] - 'a'))
                         % hashmod[modi];
                for(int i = 1;i < logmaxs && qlen * (1 << i) <= plen;i++)
                    quehash[modi][i] = (quehash[modi][i - 1] + 
                        quehash[modi][i - 1] * powmod[modi][qlen * (1 << (i - 1))]) 
                        % hashmod[modi];
            }
            // printf("que\t\t");
            // for(int i = 0;i < qlen;i++)
            //     printf("%lld " , quehash[0][i]);
            // puts("");
            int pos = -1 , cnt = 0;bool suc , suc2 = false;
            while(cnt < qlen)
            {
                for(int s = maxs >> 1 , spow = logmaxs - 1;s;s >>= 1 , spow--)
                {
                    if(pos + s * qlen >= plen)continue;
                    // printf("pos = %d , spow = %d , s = %d\n" , pos , spow , s);
                    suc = true;
                    if(spow < 0){puts("a");return 0;}
                    if(pos < 0 && pos != -1){puts("b");return 0;}
                    if(pos >= plen){puts("c");return 0;}
                    for(int modi = 0;modi < hashnum;modi++)
                    {
                        if(pos == -1)
                        {
                            // printf("que = %lld , ")
                            if(parhash[modi][s * qlen - 1] != quehash[modi][spow])
                                {suc = false;break;}
                        }
                        else if(((parhash[modi][pos + s * qlen] - parhash[modi][pos] * 
                            powmod[modi][s * qlen]) % hashmod[modi] + hashmod[modi])
                             % hashmod[modi] != quehash[modi][spow])
                            {suc = false;break;}
                    }
                    // cout << "suc = " << suc << endl;
                    if(suc)pos += s * qlen;
                }
                if(pos == plen - 1)suc2 = true;
                pos++;cnt++;
            }
            puts(suc2 ? "Yes" : "No");
        }
    }
    return 0;
}