字符串算法模板

  1 #include<algorithm>
  2 #include<iostream>
  3 #include<cstdlib>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<string>
  7 #include<cmath>
  8 #include<ctime>
  9 #include<queue>
 10 #include<stack>
 11 #include<map>
 12 #include<set>
 13 #define rre(i,r,l) for(int i=(r);i>=(l);i--)
 14 #define re(i,l,r) for(int i=(l);i<=(r);i++)
 15 #define Clear(a,b) memset(a,b,sizeof(a))
 16 #define inout(x) printf("%d",(x))
 17 #define douin(x) scanf("%lf",&x)
 18 #define strin(x) scanf("%s",(x))
 19 #define LLin(x) scanf("%lld",&x)
 20 #define op operator
 21 #define CSC main
 22 typedef unsigned long long ULL;
 23 typedef const int cint;
 24 typedef long long LL;
 25 using namespace std;
 26 void inin(int &ret)
 27 {
 28     ret=0;int f=0;char ch=getchar();
 29     while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
 30     while(ch>='0'&&ch<='9')ret*=10,ret+=ch-'0',ch=getchar();
 31     ret=f?-ret:ret;
 32 }
 33 namespace sa//uoj#35
 34 {
 35     char s[100050];
 36     int sa[100050],t[100050],t2[100050],c[100050],n,height[100050];
 37     void build_sa(int m)
 38     {
 39         int *x=t,*y=t2;
 40         re(i,0,m-1)c[i]=0;
 41         re(i,0,n-1)c[x[i]=s[i]]++;
 42         re(i,1,m-1)c[i]+=c[i-1];
 43         rre(i,n-1,0)sa[--c[x[i]]]=i;
 44         for(int k=1;k<=n;k<<=1)
 45         {
 46             int p=0;
 47             rre(i,n-1,n-k)y[p++]=i;
 48             re(i,0,n-1)if(sa[i]>=k)y[p++]=sa[i]-k;
 49             re(i,0,m-1)c[i]=0;
 50             re(i,0,n-1)c[x[y[i]]]++;
 51             re(i,0,m-1)c[i]+=c[i-1];
 52             rre(i,n-1,0)sa[--c[x[y[i]]]]=y[i];
 53             swap(x,y),x[sa[0]]=0,p=1;
 54             re(i,1,n-1)x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
 55             if(p>=n)break;
 56             m=p;
 57         }
 58     }
 59     void build_height()
 60     {
 61         re(i,0,n-1)c[sa[i]]=i;
 62         int k=0;
 63         re(i,0,n-1)
 64         {
 65             if(!c[i])continue;
 66             if(k)k--;
 67             int j=sa[c[i]-1];
 68             while(s[i+k]==s[j+k])k++;
 69             height[c[i]]=k;
 70         }
 71     }
 72     void solve()
 73     {
 74         strin(s);n=strlen(s);
 75         build_sa(200);
 76         build_height();
 77         re(i,0,n-1)printf("%d%c",sa[i]+1,i==n-1?'
':' ');
 78         re(i,1,n-1)printf("%d%c",height[i],i==n-1?'
':' ');
 79     }
 80 }
 81 namespace acm//bzoj3172
 82 {
 83     int ch[1000010][26],pre[1000010],last[1000010],sum[1000010],tag[1000010],ed;
 84     char s[1000010];
 85     int wei[222];
 86     void add(int id)
 87     {
 88         int len=strlen(s),temp=0;
 89         re(i,0,len-1)
 90         {
 91             int c=s[i]-'a';
 92             if(!ch[temp][c])ch[temp][c]=++ed;
 93             temp=ch[temp][c];
 94             sum[temp]++;
 95         }
 96         wei[id]=temp;
 97         tag[temp]=id;
 98     }
 99     queue<int>h;
100     int sta[1000010],top;
101     void getfail()
102     {
103         re(i,0,25)if(ch[0][i])pre[ch[0][i]]=0,h.push(ch[0][i]);
104         while(!h.empty())
105         {
106             int x=h.front();h.pop();
107             sta[++top]=x;
108             re(i,0,25)
109             {
110                 if(!ch[x][i])
111                 {
112                     ch[x][i]=ch[pre[x]][i];
113                     continue;
114                 }
115                 int vv=ch[x][i];
116                 int k=pre[x];
117                 pre[vv]=ch[k][i];
118                 last[vv]=tag[pre[vv]]?pre[vv]:last[pre[vv]];
119                 h.push(vv);
120             }
121         }
122     }
123     int n;
124     void solve()
125     {
126         inin(n);
127         re(i,1,n)strin(s),add(i);
128         getfail();
129         while(top)sum[pre[sta[top]]]+=sum[sta[top]],top--;
130         re(i,1,n)printf("%d
",sum[wei[i]]);
131     }
132     
133 }
134 namespace kmp//bzoj1355
135 {
136     char a[1000010],b[1000010];
137     int n,m,pre[1000010];
138     void getpre(char *s)
139     {
140         int k=0;n=strlen(s+1);
141         re(i,2,n)
142         {
143             while(k&&s[i]!=s[k+1])k=pre[k];
144             if(s[i]==s[k+1])k++;
145             pre[i]=k;
146         }
147     }
148     int kmp(char *chang,char *duan)
149     {
150         getpre(duan);
151         int k=0;n=strlen(chang+1),m=strlen(duan+1);
152         re(i,1,n)
153         {
154             while(k&&chang[i]!=duan[k+1])k=pre[k];
155             if(chang[i]==duan[k+1])
156             {
157                 k++;
158                 if(k==m)return i-m+1;
159             }
160         }
161         return -1;
162     }
163     void solve()
164     {
165         inin(n);
166         strin(a+1);
167         getpre(a);
168         printf("%d",n-pre[n]);
169     }
170 }
171 namespace exkmp//bzoj3670
172 {
173     char s[1000010],t[1000010];int pre[1000010],Max[1000010],sum[1000010];
174     const int mod=1e9+7;
175     void getpre(char *s)
176     {
177         int len=strlen(s),a=0;
178         pre[0]=len;
179         while(a<len-1&&s[a]==s[a+1])a++;
180         pre[1]=a;
181         a=1;
182         re(k,2,len-1)
183         {
184             int p=a+pre[a]-1,l=pre[k-a];
185             if(k-1+l>=p)
186             {
187                 int j=(p-k+1)>0?(p-k+1):0;
188                 while(k+j<len&&s[k+j]==s[j])j++;
189                 pre[k]=j;
190                 a=k;
191             }
192             else pre[k]=l;
193         }
194     }
195     void getextend(char *s,char *t)
196     {
197         int n=strlen(s),m=strlen(t),a=0;
198         getpre(s);
199         while(a<n-1&&s[a]==t[a+1])a++;
200         Max[0]=a;
201         a=1;
202         re(k,1,n-1)
203         {
204             int p=a+Max[a]-1,l=pre[k-a];
205             if(k+l-1>=p)
206             {
207                 int j=(p-k+1)>0?(p-k+1):0;
208                 while(k+j<m&&s[k+j]==t[j])j++;
209                 Max[k]=j;
210                 a=k;
211             }
212             else Max[k]=l;
213         }
214     }
215     int n,T;
216     void solve()
217     {
218         inin(n);
219         while(n--)
220         {
221             T++;
222             strin(s);
223             int len=strlen(s);
224             getpre(s);
225             re(i,1,len-1)
226             {
227                 int r=min(i<<1,pre[i]+i);
228                 if(t[i]!=T)t[i]=T,sum[i]=1;
229                 else sum[i]++;
230                 if(t[r]!=T)t[r]=T,sum[r]=-1;
231                 else sum[r]--;
232             }
233             if(t[0]!=T)t[0]=T,sum[0]=0;
234             LL ans=sum[0]+1;
235             re(i,1,len-1)
236             {
237                 if(t[i]!=T)t[i]=T,sum[i]=0;
238                 sum[i]+=sum[i-1];ans=ans*(sum[i]+1)%mod;
239             }
240             printf("%lld
",ans);
241         }
242     }
243 }
244 namespace pam
245 {
246     const int xxxx=600010;//length
247     int ch[xxxx][26];//son
248     int pre[xxxx];//fail
249     int sum[xxxx];//times
250     int len[xxxx];//Max_length
251     int ss[xxxx];//string
252     int num[xxxx];//numbers
253     int last,n,ed=-1;
254     int newnode(int x)//you_know
255     {
256         len[++ed]=x;
257         return ed;
258     }
259     void init()//pretreatment
260     {
261         newnode(0),newnode(-1);
262         last=n=0;ss[n]=-1,pre[0]=pre[1]=1;
263     }
264     int getfail(int x)//you_know
265     {
266         while(ss[n-len[x]-1]!=ss[n])x=pre[x];
267         return x;
268     }
269     void add(int c)//add_a_char
270     {
271         c-='a';
272         ss[++n]=c;
273         int temp=getfail(last);
274         if(!ch[temp][c])
275         {
276             int now=newnode(len[temp]+2);
277             int k=getfail(pre[temp]);
278             pre[now]=ch[k][c];
279             ch[temp][c]=now;
280             num[now]=num[pre[now]]+1;
281         }
282         last=ch[temp][c];
283         sum[last]++;
284     }
285     void add(char *s)//add_a_string
286     {
287         int limit=strlen(s);
288         re(i,0,limit-1)add(s[i]);
289     }
290     void count()//clac_times
291     {
292         rre(i,ed,1)sum[pre[i]]+=sum[i];
293     }
294 }
295 namespace manacher
296 {
297     const int xxxx=5000050;
298     char s[xxxx];
299     int n,ans,len[xxxx];
300     void solve()
301     {
302         strin(s+1);int m=strlen(s+1);
303         rre(i,m,1)s[(i<<1)-1]=s[i],s[i<<1]='$';
304         s[0]='$';n=m<<1;
305         for(int i=1,j=0,k;i<n;i+=k,j=max(j-k,0))
306         {
307             while(i+j+1<=n&&s[i-j-1]==s[i+j+1])j++;
308             len[i]=j;ans=max(ans,len[i]);
309             for(k=1;k<=j&&len[i]-k!=len[i-k];k++)
310                 len[i+k]=min(len[i]-k,len[i-k]);
311         }
312         printf("%d",ans);
313     }
314 }
315 int main()
316 {
317      return 0;
318 }