自动机+字典树)"/>
牛客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 }
更多推荐
牛客15334 Easygoing Single Tune Circulation(后缀自动机+字典树)
发布评论