好像序列自動機還沒有寫過…

串長為n的串共有n+1個節點，除了串中的n個節點，還有一個空的根節點放在串首。每個節點至多有26條出邊，每條邊連向它之后的第一個字符。

串中的任意一個子序列對應了一條根到某個節點的路徑。且每條路徑對應一個不同的子序列。

每個節點的parent是這個字母上一次出現的位置。更新只要沿parent指針掃描即可。

FJOI2016 所有公共子序列問題

這題暴力建trie能過80真是悲傷（因為按FJOI命題風格這題沒有寫數據范圍

建完序列自動機暴力DP即可

#include <iostream> #include <stdio.h> #include <stdlib.h> #include <algorithm> #include <string.h> #include <vector> #include <limits> #include <set> #include <map> using namespace std; #define SZ 3333 int ys[2333],fys[2333]; #define M 60 struct Seq_A_M { int par[SZ],ch[SZ][62],lst[62],C,rot; Seq_A_M() {C=rot=1;for(int i=0;i<M;i++) lst[i]=rot; } void ins(char c) {++C; par[C]=lst[c];for(int i=0;i<M;i++){for(int g=lst[i];g&&!ch[g][c];g=par[g]) ch[g][c]=C;}lst[c]=C; } }S_A,S_B; int n,m; typedef long long ll; ll dp[SZ][SZ]; char x[SZ],y[SZ]; ll getdp(int a,int b) {if(!a||!b) return 0;if(dp[a][b]>=0) return dp[a][b];long long ans=1;for(int i=0;i<M;i++) ans+=getdp(S_A.ch[a][i],S_B.ch[b][i]);return dp[a][b]=ans; } char s[233333]; void tryy(int a,int b,int cl) {if(!a||!b) return;s[cl]=0; printf("%s\n",s);for(int i=0;i<M;i++){s[cl]=fys[i]; tryy(S_A.ch[a][i],S_B.ch[b][i],cl+1);} } int main() {for(int i='A';i<='Z';i++) ys[i]=i-'A', fys[i-'A']=i;for(int i='a';i<='z';i++) ys[i]=i-'a'+26, fys[i-'a'+26]=i;int k=0;scanf("%d%d%s%s%d",&n,&m,x,y,&k);for(int i=0;i<n;i++) S_A.ins(ys[x[i]]);for(int i=0;i<m;i++) S_B.ins(ys[y[i]]);if(k==1) tryy(1,1,0);memset(dp,-1,sizeof(dp));printf("%lld\n",getdp(1,1)); }

四校聯考 公共串問題

還是暴力DP。注意一些細節。

#include <iostream> #include <stdio.h> #include <stdlib.h> #include <algorithm> #include <string.h> #include <vector> #include <limits> #include <set> #include <map> using namespace std; int MOD=998244353; #define SZ 4008 #define S 26 //字符集 struct AM { int rot,ch[SZ][S],C,cnt[SZ]; }; struct SeqAM: public AM { int par[SZ],lst[S]; SeqAM() {C=rot=1;for(int i=0;i<S;i++) lst[i]=rot; } void ins(char c) {++C; par[C]=lst[c];for(int i=0;i<S;i++){for(int g=lst[i];g&&!ch[g][c];g=par[g]) ch[g][c]=C;}lst[c]=C; } void getcnt() {for(int i=1;i<=C;i++) cnt[i]=1;for(int i=C;i>=1;i--){for(int j=0;j<S;j++) cnt[i]+=cnt[ch[i][j]], cnt[i]%=MOD;} } }SeqA,SeqB; struct SufAM: public AM { int ml[SZ],fail[SZ],lst,cl,qzh[SZ],od[SZ]; SufAM() {C=lst=rot=1; cl=0;} void ins(char c) {int x=++C,len=++cl,p=lst;lst=x; ml[x]=len;for(;p&&!ch[p][c];p=fail[p]) ch[p][c]=x;if(!p) fail[x]=rot;else if(ml[ch[p][c]]==ml[p]+1) fail[x]=ch[p][c];else{int chh=ch[p][c],cm=++C;ml[cm]=ml[p]+1; fail[cm]=fail[chh];for(int i=0;i<S;i++) ch[cm][i]=ch[chh][i];fail[chh]=fail[x]=cm;for(;ch[p][c]==chh;p=fail[p]) ch[p][c]=cm;} } void getcnt() {for(int i=0;i<SZ;i++) qzh[i]=0;for(int i=1;i<=C;i++) qzh[ml[i]]++;for(int i=1;i<SZ;i++) qzh[i]+=qzh[i-1];for(int i=1;i<=C;i++) od[qzh[ml[i]]--]=i;for(int i=1;i<=C;i++) cnt[i]=1;for(int i=C;i>=1;i--){for(int j=0;j<S;j++) cnt[od[i]]+=cnt[ch[od[i]][j]], cnt[od[i]]%=MOD;} } }SufA,SufB; void prtat(AM& s) {for(int i=1;i<=s.C;i++){for(int j=0;j<S;j++) if(s.ch[i][j]) printf("%d->%d[label=%c];\n",i,s.ch[i][j],j+'a');} } AM *cur,*curb; int dp2[SZ][SZ]; int dfs(int a,int b) {if(!a) return 0;if(!b) return cur->cnt[a];if(dp2[a][b]>=0) return dp2[a][b];int ans=0;for(int i=0;i<S;i++) ans+=dfs(cur->ch[a][i],curb->ch[b][i]), ans%=MOD;return dp2[a][b]=ans; } int getdp(AM& a,AM& b) {cur=&a; curb=&b;for(int i=1;i<=a.C;i++)for(int j=1;j<=b.C;j++) dp2[i][j]=-1;dfs(a.rot,b.rot);return dp2[a.rot][b.rot]; } char A[SZ],B[SZ]; void prt(int a) {a=(a%MOD+MOD)%MOD;printf("%d\n",a); } int main() {scanf("%s%s",A,B);for(int i=0;A[i];i++) SeqA.ins(A[i]-'a'), SufA.ins(A[i]-'a');for(int i=0;B[i];i++) SeqB.ins(B[i]-'a'), SufB.ins(B[i]-'a');SeqA.getcnt(); SeqB.getcnt();SufA.getcnt(); SufB.getcnt();int AseqBseq=getdp(SeqA,SeqB);int AseqBsuf=getdp(SeqA,SufB);int AsufBseq=getdp(SufA,SeqB);int AsufBsuf=getdp(SufA,SufB);prt(AsufBsuf);prt(AsufBseq);prt(AseqBsuf);prt(AseqBseq); }

bzoj4032 最短不公共子串

#include <iostream> #include <stdio.h> #include <stdlib.h> #include <algorithm> #include <string.h> #include <vector> #include <limits> #include <set> #include <map> using namespace std; int MOD=998244353; #define SZ 4008 #define S 26 //字符集 struct AM { int rot,ch[SZ][S],C,cnt[SZ]; }; struct SeqAM: public AM { int par[SZ],lst[S]; SeqAM() {C=rot=1;for(int i=0;i<S;i++) lst[i]=rot; } void ins(char c) {++C; par[C]=lst[c];for(int i=0;i<S;i++){for(int g=lst[i];g&&!ch[g][c];g=par[g]) ch[g][c]=C;}lst[c]=C; } void getcnt() {for(int i=1;i<=C;i++) cnt[i]=1;for(int i=C;i>=1;i--){for(int j=0;j<S;j++) cnt[i]+=cnt[ch[i][j]], cnt[i]%=MOD;} } }SeqA,SeqB; struct SufAM: public AM { int ml[SZ],fail[SZ],lst,cl,qzh[SZ],od[SZ]; SufAM() {C=lst=rot=1; cl=0;} void ins(char c) {int x=++C,len=++cl,p=lst;lst=x; ml[x]=len;for(;p&&!ch[p][c];p=fail[p]) ch[p][c]=x;if(!p) fail[x]=rot;else if(ml[ch[p][c]]==ml[p]+1) fail[x]=ch[p][c];else{int chh=ch[p][c],cm=++C;ml[cm]=ml[p]+1; fail[cm]=fail[chh];for(int i=0;i<S;i++) ch[cm][i]=ch[chh][i];fail[chh]=fail[x]=cm;for(;ch[p][c]==chh;p=fail[p]) ch[p][c]=cm;} } void getcnt() {for(int i=0;i<SZ;i++) qzh[i]=0;for(int i=1;i<=C;i++) qzh[ml[i]]++;for(int i=1;i<SZ;i++) qzh[i]+=qzh[i-1];for(int i=1;i<=C;i++) od[qzh[ml[i]]--]=i;for(int i=1;i<=C;i++) cnt[i]=1;for(int i=C;i>=1;i--){for(int j=0;j<S;j++) cnt[od[i]]+=cnt[ch[od[i]][j]], cnt[od[i]]%=MOD;} } }SufA,SufB; void prtat(AM& s) {for(int i=1;i<=s.C;i++){for(int j=0;j<S;j++) if(s.ch[i][j]) printf("%d->%d[label=%c];\n",i,s.ch[i][j],j+'a');} } int dep[SZ][SZ]; int qa[SZ*SZ],qb[SZ*SZ]; int bfs(AM& a,AM& b) {memset(dep,0,sizeof(dep));int h=0,t=1; qa[0]=a.rot; qb[0]=b.rot; dep[qa[0]][qb[0]]=1;while(h!=t){int ca=qa[h],cb=qb[h]; ++h;for(int j=0;j<S;j++){int _ca=a.ch[ca][j],_cb=b.ch[cb][j];if(dep[_ca][_cb]||!_ca) continue;if(!_cb) return dep[ca][cb];dep[_ca][_cb]=dep[ca][cb]+1;qa[t]=_ca; qb[t]=_cb; ++t;}}return -1; } #define prt(x) printf("%d\n",x) char A[SZ],B[SZ]; int main() {scanf("%s%s",A,B);for(int i=0;A[i];i++) SeqA.ins(A[i]-'a'), SufA.ins(A[i]-'a');for(int i=0;B[i];i++) SeqB.ins(B[i]-'a'), SufB.ins(B[i]-'a');SeqA.getcnt(); SeqB.getcnt();SufA.getcnt(); SufB.getcnt();int AseqBseq=bfs(SeqA,SeqB);int AseqBsuf=bfs(SeqA,SufB);int AsufBseq=bfs(SufA,SeqB);int AsufBsuf=bfs(SufA,SufB);prt(AsufBsuf);prt(AsufBseq);prt(AseqBsuf);prt(AseqBseq); }

轉載于:https://www.cnblogs.com/zzqsblog/p/5371808.html

總結

以上是生活随笔為你收集整理的后缀自动机序列自动机综合的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。