题意

给定n个字符串 s[i]，再给出m个查询的字符串 t[i]，问 t[i] 是否为某个 s[i] 循环无限次的子串。

题解

分成两种情况
① t[i] 比 s[j] 短， 这个时候可以用后缀自动机，把每个 s[j] 重复一次，然后放到SAM中，这样直接每次直接查询就好了。当然，因为是有t（t<=1e5）组数据，全部初始化肯定会超时的，所以下一个要用到哪部分哪部分就初始化，这样最多初始化1e6次，因为所有的长度不会超过1e6。
② t[i] 比 s[j] 长，这样的话就不能用后缀自动机了，因为并不知道 t[i] 到底是 s[j] 重复了几次的子串。考虑到 t[i] 如果是某个 s[j] 循环无限次的子串，那么他一定是有循环节的，因为不知道有没有循环节，所以找到第一个最长的且每个字母只出现了一次的子串，并用最小表示法表示，然后在一颗插入了每个 s[j] 的最小表示法的字典树中查找是否有这个子串，如果有的话，构造长度为 | t[i] |，以该子串为循环节的串，如果这个串就是 t[i] 那么说明有该串，否则没有。当然，字典树的初始化也会卡，所以同样的边用边初始化下一个即将要用的。

代码 

#include<bits/stdc++.h>
using namespace std;
 
const int maxn=1e6+10;
 
struct SAM
{
    int mxlen[maxn<<1],link[maxn<<1],nt[maxn<<1][26];
    int sz,last,len;
    void init()
    {
       memset(nt[0],0,sizeof(nt[0]));
       mxlen[0]=0;
       link[0]=-1;
       sz=1;
       last=0;
    }
 
    void extend(int c)
    {
        c-='a';
        int cur=sz++;
        mxlen[cur]=mxlen[last]+1;
        int p=last;
        memset(nt[cur],0,sizeof(nt[cur]));
        while(p!=-1&&!nt[p][c]){
            nt[p][c]=cur;
            p=link[p];
        }
        if(p==-1) link[cur]=0;
        else{
            int q=nt[p][c];
            if(mxlen[p]+1==mxlen[q]) link[cur]=q;
            else{
                int clone=sz++;
                mxlen[clone]=mxlen[p]+1;
                memcpy(nt[clone],nt[q],sizeof(nt[q]));
                link[clone]=link[q];
                while(p!=-1&&nt[p][c]==q){
                    nt[p][c]=clone;
                    p=link[p];
                }
                link[q]=link[cur]=clone;
            }
        }
        last=cur;
    }
    bool query(string s)
    {
        int p=0;
        for(int i=0;i<s.size();i++){
            int c=s[i]-'a';
            if(!nt[p][c]) return 0;
            p=nt[p][c];
        }
        return 1;
    }
}sam;
 
struct Trie
{
    int tree[maxn][30];
    int color[maxn];
    int k=1;
 
    int newnode()
    {
        memset(tree[k],0,sizeof(tree[k]));
        color[k]=0;
        return k++;
    }
 
    void init()
    {
        color[0]=0;
        memset(tree[0],0,sizeof(tree[0]));
        k=1;
    }
 
    void insert(string a)
    {
        int p=0;
        int len=a.size();
        for(int i=0;i<len;i++){
            int c=a[i]-'a';
            if(!tree[p][c]) {
                tree[p][c]=newnode();
            }
            p=tree[p][c];
        }
        color[p]++;
    }
    int query(string a)
    {
        int p=0;
        int len=a.size();
        for(int i=0;i<len;i++){
            int c=a[i]-'a';
            if(!tree[p][c]) return 0;
            p=tree[p][c];
        }
        return color[p];
    }
}trie;
 
const int maxm=1e5+10;
string s[maxm];
 
string get_min(string s)
{
    string t;
    int p=26,pos=0;
    for(int i=0;i<s.size();i++){
        if(s[i]-'a'<=p) p=s[i]-'a',pos=i;
    }
    t=s.substr(pos);
    t+=s.substr(0,pos);
    return t;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    int k=1;
    while(T--){
        sam.init();
        trie.init();
        cout<<"Case #"<<k++<<":"<<endl;
        int n;
        cin>>n;
        for(int i=0;i<n;i++){
            cin>>s[i];
            string t=get_min(s[i]);
            trie.insert(t);
        }
        for(int i=0;i<n;i++){
            sam.last=0;
            for(int j=0;j<s[i].size();j++) sam.extend(s[i][j]);
            for(int j=0;j<s[i].size();j++) sam.extend(s[i][j]);
        }
        int m;
        cin>>m;
        while(m--){
            string a;
            cin>>a;
            if(sam.query(a)){
                cout<<"YES"<<endl;
                continue;
            }
            int pos=a.size();
            for(int i=1;i<pos;i++){
                if(a[i]==a[0]){
                    pos=i;
                    break;
                }
            }
            string t=a.substr(0,pos);
            string tt=get_min(t);
            if(trie.query(tt)){
                string p;
                for(int i=0;i<a.size();i++){
                    p+=t[i%t.size()];
                }
                if(p==a){
                    cout<<"YES"<<endl;
                    continue;
                }
            }
            cout<<"NO"<<endl;
        }
    }
    return 0;
}