牛客15334 Easygoing Single Tune Circulation（后缀自动机+字典树）

自动机+字典树）"/>

牛客15334 Easygoing Single Tune Circulation（后缀自动机+字典树）

传送门：Easygoing Single Tune Circulation

题意

给定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] 那么说明有该串，否则没有。当然，字典树的初始化也会卡，所以同样的边用边初始化下一个即将要用的。

代码

  1 #include<bits/stdc++.h>2 using namespace std;3   4 const int maxn=1e6+10;5   6 struct SAM7 {8     int mxlen[maxn<<1],link[maxn<<1],nt[maxn<<1][26];9     int sz,last,len;10     void init()11     {12        memset(nt[0],0,sizeof(nt[0]));13        mxlen[0]=0;14        link[0]=-1;15        sz=1;16        last=0;17     }18   19     void extend(int c)20     {21         c-='a';22         int cur=sz++;23         mxlen[cur]=mxlen[last]+1;24         int p=last;25         memset(nt[cur],0,sizeof(nt[cur]));26         while(p!=-1&&!nt[p][c]){27             nt[p][c]=cur;28             p=link[p];29         }30         if(p==-1) link[cur]=0;31         else{32             int q=nt[p][c];33             if(mxlen[p]+1==mxlen[q]) link[cur]=q;34             else{35                 int clone=sz++;36                 mxlen[clone]=mxlen[p]+1;37                 memcpy(nt[clone],nt[q],sizeof(nt[q]));38                 link[clone]=link[q];39                 while(p!=-1&&nt[p][c]==q){40                     nt[p][c]=clone;41                     p=link[p];42                 }43                 link[q]=link[cur]=clone;44             }45         }46         last=cur;47     }48     bool query(string s)49     {50         int p=0;51         for(int i=0;i<s.size();i++){52             int c=s[i]-'a';53             if(!nt[p][c]) return 0;54             p=nt[p][c];55         }56         return 1;57     }58 }sam;59   60 struct Trie61 {62     int tree[maxn][30];63     int color[maxn];64     int k=1;65   66     int newnode()67     {68         memset(tree[k],0,sizeof(tree[k]));69         color[k]=0;70         return k++;71     }72   73     void init()74     {75         color[0]=0;76         memset(tree[0],0,sizeof(tree[0]));77         k=1;78     }79   80     void insert(string a)81     {82         int p=0;83         int len=a.size();84         for(int i=0;i<len;i++){85             int c=a[i]-'a';86             if(!tree[p][c]) {87                 tree[p][c]=newnode();88             }89             p=tree[p][c];90         }91         color[p]++;92     }93     int query(string a)94     {95         int p=0;96         int len=a.size();97         for(int i=0;i<len;i++){98             int c=a[i]-'a';99             if(!tree[p][c]) return 0;
100             p=tree[p][c];
101         }
102         return color[p];
103     }
104 }trie;
105   
106 const int maxm=1e5+10;
107 string s[maxm];
108   
109 string get_min(string s)
110 {
111     string t;
112     int p=26,pos=0;
113     for(int i=0;i<s.size();i++){
114         if(s[i]-'a'<=p) p=s[i]-'a',pos=i;
115     }
116     t=s.substr(pos);
117     t+=s.substr(0,pos);
118     return t;
119 }
120   
121 int main()
122 {
123     ios::sync_with_stdio(false);
124     cin.tie(0);
125     cout.tie(0);
126     int T;
127     cin>>T;
128     int k=1;
129     while(T--){
130         sam.init();
131         trie.init();
132         cout<<"Case #"<<k++<<":"<<endl;
133         int n;
134         cin>>n;
135         for(int i=0;i<n;i++){
136             cin>>s[i];
137             string t=get_min(s[i]);
138             trie.insert(t);
139         }
140         for(int i=0;i<n;i++){
141             sam.last=0;
142             for(int j=0;j<s[i].size();j++) sam.extend(s[i][j]);
143             for(int j=0;j<s[i].size();j++) sam.extend(s[i][j]);
144         }
145         int m;
146         cin>>m;
147         while(m--){
148             string a;
149             cin>>a;
150             if(sam.query(a)){
151                 cout<<"YES"<<endl;
152                 continue;
153             }
154             int pos=a.size();
155             for(int i=1;i<pos;i++){
156                 if(a[i]==a[0]){
157                     pos=i;
158                     break;
159                 }
160             }
161             string t=a.substr(0,pos);
162             string tt=get_min(t);
163             if(trie.query(tt)){
164                 string p;
165                 for(int i=0;i<a.size();i++){
166                     p+=t[i%t.size()];
167                 }
168                 if(p==a){
169                     cout<<"YES"<<endl;
170                     continue;
171                 }
172             }
173             cout<<"NO"<<endl;
174         }
175     }
176     return 0;
177 }