【系列】后缀自动机

bzoj 2882 工艺

题目大意：

求一个数列的最小表示法

思路：

在后缀自动机上直接沿最小的边跑n步即可（学习了一波map的高端操作

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<cstring>
 7 #include<vector>
 8 #include<queue>
 9 #include<map>
10 #define rep(i,s,t) for(register int i=(s);i<=(t);++i)
11 #define dwn(i,s,t) for(register int i=(s);i>=(t);--i)
12 #define ren for(register int i=fst[x];i;i=nxt[i])
13 #define Fill(x,t) memset(x,t,sizeof(x))
14 #define ll long long
15 #define inf 2139062143
16 #define MAXN 1200100
17 using namespace std;
18 inline int read()
19 {
20     int x=0,f=1;char ch=getchar();
21     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
22     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
23     return x*f;
24 }
25 int n,a[MAXN],rt,lst,tot,sz[MAXN],mxlen[MAXN],rnk[MAXN],cnt[MAXN],fa[MAXN];
26 map<int,int> tr[MAXN];
27 inline void extend(int c)
28 {
29     int p=lst,np=lst=++tot;mxlen[np]=mxlen[p]+1,sz[np]=1;
30     for(;p&&!tr[p][c];p=fa[p]) tr[p][c]=np;
31     if(!p) {fa[np]=rt;return ;}
32     int q=tr[p][c];if(mxlen[q]==mxlen[p]+1) {fa[np]=q;return ;}
33     int nq=++tot;mxlen[nq]=mxlen[p]+1;
34     tr[nq]=tr[q],fa[nq]=fa[q],fa[np]=fa[q]=nq;
35     for(;p&&tr[p][c]==q;p=fa[p]) tr[p][c]=nq;
36 }
37 int main()
38 {
39     rt=lst=tot=1;n=read();rep(i,1,n) a[i]=read();
40     rep(i,1,n) a[i+n]=a[i];rep(i,1,n<<1) extend(a[i]);
41     int pos=rt;
42     while(n--)
43     {
44         printf("%d ",tr[pos].begin()->first);
45         pos=tr[pos].begin()->second;
46     }
47 }

View Code

bzoj 4516 生成魔咒

题目大意：、

每读入一个数输出当前数列有多少个本质不同的子串

思路：

加入一个数的时候对答案的贡献为有多少个节点中新出现了这个数

则每个点对答案的贡献为$mxlen_i-mxlen_{fa[i]}$ 求一下即可

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<cstring>
 7 #include<vector>
 8 #include<queue>
 9 #include<map>
10 #define rep(i,s,t) for(register int i=(s);i<=(t);++i)
11 #define dwn(i,s,t) for(register int i=(s);i>=(t);--i)
12 #define ren for(register int i=fst[x];i;i=nxt[i])
13 #define Fill(x,t) memset(x,t,sizeof(x))
14 #define ll long long
15 #define inf 2139062143
16 #define MAXN 200100
17 #define MOD 998244353
18 using namespace std;
19 inline int read()
20 {
21     int x=0,f=1;char ch=getchar();
22     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
23     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
24     return x*f;
25 }
26 int rt,n,lst,fa[MAXN],sz[MAXN],mxlen[MAXN],tot;
27 int g[MAXN];
28 ll ans;
29 map<int,int> tr[MAXN];
30 void extend(int c)
31 {
32     int p=lst,np=lst=++tot;mxlen[np]=mxlen[p]+1;
33     for(;p&&!tr[p][c];p=fa[p]) tr[p][c]=np;
34     if(!p) {fa[np]=rt;ans+=mxlen[np]-mxlen[rt];return ;}
35     int q=tr[p][c];
36     if(mxlen[q]==mxlen[p]+1) {fa[np]=q;ans+=mxlen[np]-mxlen[q];return ;}
37     int nq=++tot;mxlen[nq]=mxlen[p]+1;
38     tr[nq]=tr[q];ans+=mxlen[nq]-mxlen[fa[q]]-mxlen[q]+mxlen[fa[q]];
39     fa[nq]=fa[q],fa[np]=fa[q]=nq;ans+=mxlen[np]-mxlen[nq]+mxlen[q]-mxlen[nq];
40     for(;p&&tr[p][c]==q;p=fa[p]) tr[p][c]=nq;
41 }
42 int main()
43 {
44     rt=lst=tot=1;
45     n=read();rep(i,1,n) {g[i]=read();extend(g[i]);printf("%lld
",ans);}
46 }

View Code

bzoj 3879 SvT

题目大意：

一个字符串S 有一些询问,每次给出若干个后缀的起始位置求这些后缀两两之间的LCP的长度之和.一对后缀之间的LCP长度仅统计一遍

思路：

对于反串建立后缀自动机则两个后缀之间的LCP变成了两个前缀之间的LCS

于是两个串的答案就是他们lca的深度所以我们可以建虚树然后树形dp

标记一下关键点然后统计一下子树信息乘一乘

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<cstring>
 7 #include<vector>
 8 #include<queue>
 9 #include<map>
10 #define rep(i,s,t) for(register int i=(s);i<=(t);++i)
11 #define dwn(i,s,t) for(register int i=(s);i>=(t);--i)
12 #define ren for(int i=fst[x];i;i=nxt[i])
13 #define Fill(x,t) memset(x,t,sizeof(x))
14 #define ll long long
15 #define inf 2139062143
16 #define MAXN 1001000
17 using namespace std;
18 char s[MAXN];
19 int n,m,hsh[MAXN],k,g[MAXN],st[MAXN],top;
20 int rt,lst,tr[MAXN][26],tot,mxlen[MAXN],fa[MAXN];
21 int fst[MAXN],nxt[MAXN<<1],to[MAXN<<1],cnt,in[MAXN],ou[MAXN];
22 int mn[20][MAXN],l2[MAXN],dp[MAXN],tag[MAXN],dep[MAXN];
23 ll ans;
24 inline int read()
25 {
26     int x=0,f=1;char ch=getchar();
27     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
28     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
29     return x*f;
30 }
31 inline void add(int u,int v) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v;}
32 inline void extend(int c)
33 {
34     int p=lst,np=lst=++tot;mxlen[np]=mxlen[p]+1;
35     for(;p&&!tr[p][c];p=fa[p]) tr[p][c]=np;
36     if(!p) {fa[np]=rt;return ;}
37     int q=tr[p][c];if(mxlen[q]==mxlen[p]+1) {fa[np]=q;return ;}
38     int nq=++tot;mxlen[nq]=mxlen[p]+1;
39     memcpy(tr[nq],tr[q],sizeof(tr[nq])); 
40     fa[nq]=fa[q],fa[np]=fa[q]=nq;
41     for(;p&&tr[p][c]==q;p=fa[p]) tr[p][c]=nq;
42 }
43 void dfs(int x,int pa)
44 {
45     dep[x]=dep[pa]+1,in[x]=++cnt,mn[0][cnt]=x;
46     ren dfs(to[i],x);ou[x]=cnt;
47 }
48 bool cmp(const int &a,const int &b) {return in[a]<in[b];}
49 int Min(int a,int b) {return dep[a]<dep[b]?a:b;}
50 inline int lca(int a,int b)
51 {
52     if(in[a]>in[b]) swap(a,b);if(ou[a]>=ou[b]) return a;
53     int t=l2[in[b]-in[a]+1];
54     return fa[Min(mn[t][in[a]],mn[t][in[b]-(1<<t)+1])];
55 }
56 inline void ins(int x)
57 {
58     if(!top) {st[++top]=x;return ;}
59     int y=lca(st[top],x);
60     while(in[y]<in[st[top]]&&top)
61         if(in[y]>=in[st[top-1]]) {add(y,st[top--]);if(y!=st[top]) st[++top]=y;break;}
62         else {add(st[top-1],st[top]);top--;}
63     st[++top]=x;//cout<<top<<endl;
64 }
65 void Dp(int x)
66 {
67     dp[x]=tag[x]?1:0;
68     ren {Dp(to[i]);ans+=1LL*dp[x]*dp[to[i]]*mxlen[x],dp[x]+=dp[to[i]];}
69     fst[x]=0;
70 }
71 int main()
72 {
73     n=read(),m=read(),rt=lst=tot=1;scanf("%s",s+1);
74     dwn(i,n,1) {extend(s[i]-'a');hsh[i]=lst;}
75     l2[0]=-1;rep(i,1,tot) {add(fa[i],i);l2[i]=l2[i>>1]+1;}cnt=0;dfs(1,0);
76     rep(j,1,19) rep(i,1,cnt) {if(i+(1<<j)-1>cnt) break;mn[j][i]=Min(mn[j-1][i],mn[j-1][i+(1<<j-1)]);}
77     Fill(fst,0);
78     while(m--)
79     {
80         k=read();rep(i,1,k) g[i]=hsh[read()];cnt=top=0;
81         sort(g+1,g+k+1,cmp);rep(i,1,k) if(g[i]!=g[i-1]) {tag[g[i]]=1;ins(g[i]);}
82         for(;top>1;top--) add(st[top-1],st[top]);
83         ans=0LL;Dp(st[1]);
84         rep(i,1,k) if(g[i]!=g[i-1]) tag[g[i]]=0;
85         printf("%lld
",ans);
86     }
87 }

View Code

bzoj 4199 品酒大会

题目大意：

给一个字符串 S 每个位置都有一个权值$w_i$表示以这个位置开头的后缀的权值

对于一个$i∈[1,n]$ 求出满足$lcp(a,b)=i$的后缀对数量和 $w_a imes w_b$的最大值

思路：

第一问弱化版SvT 第二问求一下子树内最大值和最小值即可

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<cstring>
 7 #include<vector>
 8 #include<queue>
 9 #include<map>
10 #define rep(i,s,t) for(register int i=(s);i<=(t);++i)
11 #define dwn(i,s,t) for(register int i=(s);i>=(t);--i)
12 #define ren for(int i=fst[x];i;i=nxt[i])
13 #define Fill(x,t) memset(x,t,sizeof(x))
14 #define ll long long
15 #define inf 1152921504606846976LL
16 #define MAXN 600100
17 using namespace std;
18 char s[MAXN];
19 int n,m,hsh[MAXN];
20 int rt,lst,tr[MAXN][26],tot,mxlen[MAXN],fa[MAXN];
21 int fst[MAXN],nxt[MAXN<<1],to[MAXN<<1],cnt;
22 ll ans[MAXN],mx[MAXN],mn[MAXN],dp[MAXN],sz[MAXN];
23 inline int read()
24 {
25     int x=0,f=1;char ch=getchar();
26     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
27     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
28     return x*f;
29 }
30 inline void add(int u,int v) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v;}
31 inline void extend(int c)
32 {
33     int p=lst,np=lst=++tot;mxlen[np]=mxlen[p]+1;
34     for(;p&&!tr[p][c];p=fa[p]) tr[p][c]=np;
35     if(!p) {fa[np]=rt;return ;}
36     int q=tr[p][c];if(mxlen[q]==mxlen[p]+1) {fa[np]=q;return ;}
37     int nq=++tot;mxlen[nq]=mxlen[p]+1;
38     memcpy(tr[nq],tr[q],sizeof(tr[nq])); 
39     fa[nq]=fa[q],fa[np]=fa[q]=nq;
40     for(;p&&tr[p][c]==q;p=fa[p]) tr[p][c]=nq;
41 }
42 void mdfmx(ll x,ll &a,ll &b){if(x>a) b=a,a=x;else if(x>b) b=x;}
43 void mdfmn(ll x,ll &a,ll &b){if(x<a) b=a,a=x;else if(x<b) b=x;}
44 void dfs(int x)
45 {
46     ll res=0,submx=-inf,submn=inf;if(!mx[x]) mx[x]=-inf;if(!mn[x]) mn[x]=inf;
47     ren {dfs(to[i]);mdfmx(mx[to[i]],mx[x],submx);mdfmn(mn[to[i]],mn[x],submn);dp[mxlen[x]]+=1LL*sz[x]*sz[to[i]],sz[x]+=sz[to[i]];}
48     res=max(submx==-inf?-inf:mx[x]*submx,submn==inf?-inf:mn[x]*submn),ans[mxlen[x]]=max(ans[mxlen[x]],res);
49 }
50 int main()
51 {
52     n=read(),rt=lst=++tot;
53     scanf("%s",s+1);dwn(i,n,1) {extend(s[i]-'a');hsh[i]=lst,sz[lst]=1,ans[i]=-inf;}
54     rep(i,1,n) mx[hsh[i]]=mn[hsh[i]]=read();rep(i,1,tot) add(fa[i],i);dfs(1);
55     dwn(i,n,0) dp[i]+=dp[i+1],ans[i]=max(ans[i],dp[i+1]?ans[i+1]:-inf);
56     rep(i,0,n-1) printf("%lld %lld
",dp[i],ans[i]==-inf?0:ans[i]);
57 }

View Code

bzoj 3998 弦论

题目大意：

求字符串的第K小子串（有两种情况为本质相同的算多次或一次）

思路：

建出自动机后统计出两种情况中串出现的次数然后dfs即可

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<cstring>
 7 #include<vector>
 8 #include<queue>
 9 #include<map>
10 #define rep(i,s,t) for(register int i=(s);i<=(t);++i)
11 #define dwn(i,s,t) for(register int i=(s);i>=(t);--i)
12 #define ren for(int i=fst[x];i;i=nxt[i])
13 #define Fill(x,t) memset(x,t,sizeof(x))
14 #define ll long long
15 #define inf 1152921504606846976LL
16 #define MAXN 1000100
17 using namespace std;
18 char s[MAXN];
19 int n,m,sum[MAXN];
20 int rt,lst,tr[MAXN][26],tot,mxlen[MAXN],fa[MAXN],sz[MAXN],c[MAXN],rnk[MAXN];
21 int t,k;
22 inline int read()
23 {
24     int x=0,f=1;char ch=getchar();
25     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
26     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
27     return x*f;
28 }
29 inline void extend(int c)
30 {
31     int p=lst,np=lst=++tot;mxlen[np]=mxlen[p]+1,sz[np]=1;
32     for(;p&&!tr[p][c];p=fa[p]) tr[p][c]=np;
33     if(!p) {fa[np]=rt;return ;}
34     int q=tr[p][c];if(mxlen[q]==mxlen[p]+1) {fa[np]=q;return ;}
35     int nq=++tot;mxlen[nq]=mxlen[p]+1;
36     memcpy(tr[nq],tr[q],sizeof(tr[nq])); 
37     fa[nq]=fa[q],fa[np]=fa[q]=nq;
38     for(;p&&tr[p][c]==q;p=fa[p]) tr[p][c]=nq;
39 }
40 inline void build()
41 {
42     rep(i,1,tot) c[mxlen[i]]++;rep(i,1,n) c[i]+=c[i-1];
43     rep(i,1,tot) rnk[c[mxlen[i]]--]=i;int p;
44     dwn(i,tot,1) p=rnk[i],sz[fa[p]]=t?sz[fa[p]]+sz[p]:1;
45     sz[rt]=0;dwn(i,tot,1) {p=rnk[i],sum[p]=sz[p];rep(j,0,25) sum[p]+=sum[tr[p][j]];}
46 }
47 void dfs(int x)
48 {
49     k-=sz[x];if(k==0) return ;
50     rep(i,0,25) if(k<=sum[tr[x][i]]) {putchar(i+'a');dfs(tr[x][i]);return ;}else k-=sum[tr[x][i]];
51 }
52 int main()
53 {
54     rt=lst=++tot;scanf("%s",s+1);n=strlen(s+1);
55     rep(i,1,n) extend(s[i]-'a');t=read(),k=read();
56     build();if(sum[1]>=k) dfs(1);else puts("-1");
57 }

View Code

bzoj 4566 找相同字符

题目大意：

两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同

思路：

1.对第一个串建自动机然后拿第二个串在自动机上跑

对于经过的每个点x，对答案的贡献为树上所有祖先的$right$集合大小乘出现次数即$size$

每个点的贡献是(匹配长度-该点$maxlen$)乘该点$size$

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<vector>
 8 #include<queue>
 9 #include<map>
10 #include<set>
11 #include<complex>
12 #include<iomanip>
13 #define Fill(a,x) memset(a,x,sizeof(a))
14 #define rep(i,s,t) for(register int i=(s),i__end=(t);i<=i__end;++i)
15 #define dwn(i,s,t) for(register int i=(s),i__end=(t);i>=i__end;--i)
16 #define ren for(int i=fst[x];i;i=nxt[i])
17 #define inf 2139062143
18 #define ll long long
19 #define ull unsigned long long
20 #define MAXN 200100
21 #define MOD 998244353 
22 using namespace std;
23 inline int read()
24 {
25     int x=0,f=1;char ch=getchar();
26     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
27     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
28     return x*f;
29 }
30 int n,mxl[MAXN<<1],fa[MAXN<<1],tr[MAXN<<1][26],rt,tot,las,cnt[MAXN<<1],rnk[MAXN<<1];
31 ll dp[MAXN<<1],ans,sz[MAXN<<1];char s[MAXN];
32 void extend(int c)
33 {
34     int p=las,np=las=++tot;mxl[np]=mxl[p]+1;sz[np]++;
35     for(;p&&!tr[p][c];p=fa[p]) tr[p][c]=np;
36     if(!p) {fa[np]=rt;return ;}int q=tr[p][c];
37     if(mxl[q]==mxl[p]+1) {fa[np]=q;return ;}
38     int nq=++tot;mxl[nq]=mxl[p]+1;
39     memcpy(tr[nq],tr[q],sizeof(tr[nq]));
40     fa[nq]=fa[q],fa[np]=fa[q]=nq;
41     for(;p&&tr[p][c]==q;p=fa[p]) tr[p][c]=nq;
42 }
43 void pre()
44 {
45     rep(i,1,tot) cnt[mxl[i]]++;rep(i,1,n) cnt[i]+=cnt[i-1];
46     rep(i,1,tot) rnk[cnt[mxl[i]]--]=i;int p;
47     dwn(i,tot,1) p=rnk[i],sz[fa[p]]+=sz[p];
48     rep(i,1,tot) p=rnk[i],dp[p]=dp[fa[p]]+1LL*sz[p]*(mxl[p]-mxl[fa[p]]);
49 }
50 int main()
51 {
52     rt=tot=las=1;scanf("%s",s+1);n=strlen(s+1);rep(i,1,n) extend(s[i]-'a');
53     pre();scanf("%s",s+1);n=strlen(s+1);int p=1,c,len=0;
54     rep(i,1,n)
55     {
56         c=s[i]-'a';for(;p&&!tr[p][c];p=fa[p]);
57         if(!p) p=rt,len=0;else len=min(len,mxl[p])+1,p=tr[p][c];
58         ans+=dp[fa[p]]+1LL*(len-mxl[fa[p]])*sz[p];
59     }
60     printf("%lld
",ans);
61 }

View Code

2.建立广义后缀自动机

分别记录两个串的$sz$数组，这样每个点对答案的贡献为该点$right$集合大小乘以出现次数即$(mxlen_i-mxlen_{fa[i]}) imes sz1_i imes sz2_i$

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<vector>
 8 #include<queue>
 9 #include<map>
10 #include<set>
11 #include<complex>
12 #include<iomanip>
13 #define Fill(a,x) memset(a,x,sizeof(a))
14 #define rep(i,s,t) for(register int i=(s),i__end=(t);i<=i__end;++i)
15 #define dwn(i,s,t) for(register int i=(s),i__end=(t);i>=i__end;--i)
16 #define ren for(int i=fst[x];i;i=nxt[i])
17 #define inf 2139062143
18 #define ll long long
19 #define ull unsigned long long
20 #define MAXN 400100
21 #define MOD 998244353 
22 using namespace std;
23 inline int read()
24 {
25     int x=0,f=1;char ch=getchar();
26     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
27     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
28     return x*f;
29 }
30 int n,mxl[MAXN<<1],fa[MAXN<<1],tr[MAXN<<1][27],rt,tot,las,cnt[MAXN<<1],rnk[MAXN<<1];
31 int sz[MAXN<<1][2];char s[MAXN];
32 void extend(int c,int k)
33 {
34     int p=las,np=las=++tot;mxl[np]=mxl[p]+1;if(~k) sz[np][k]++;
35     for(;p&&!tr[p][c];p=fa[p]) tr[p][c]=np;
36     if(!p) {fa[np]=rt;return ;}int q=tr[p][c];
37     if(mxl[q]==mxl[p]+1) {fa[np]=q;return ;}
38     int nq=++tot;mxl[nq]=mxl[p]+1;
39     memcpy(tr[nq],tr[q],sizeof(tr[nq]));
40     fa[nq]=fa[q],fa[np]=fa[q]=nq;
41     for(;p&&tr[p][c]==q;p=fa[p]) tr[p][c]=nq;
42 }
43 void pre()
44 {
45     rep(i,1,tot) cnt[mxl[i]]++;rep(i,1,tot) cnt[i]+=cnt[i-1];
46     rep(i,1,tot) rnk[cnt[mxl[i]]--]=i;int p;
47     dwn(i,tot,1) p=rnk[i],sz[fa[p]][0]+=sz[p][0],sz[fa[p]][1]+=sz[p][1];
48 }
49 int main()
50 {
51     rt=tot=las=1;scanf("%s",s+1);n=strlen(s+1);rep(i,1,n) extend(s[i]-'a',0);
52     las=1;extend(26,-1);scanf("%s",s+1);n=strlen(s+1);rep(i,1,n) extend(s[i]-'a',1);
53     pre();ll ans=0;rep(i,1,tot) ans+=1LL*(mxl[i]-mxl[fa[i]])*sz[i][0]*sz[i][1];
54     printf("%lld
",ans);
55 }

View Code

【系列】 后缀自动机

【系列】后缀自动机