牛客SAM总结

Threatening Letter 简单题

#include<bits/stdc++.h> using namespace std; const int maxn=3e6+150; const int kind=26; int tot=1,las=1; int ch[maxn*2][kind]; int len[maxn*2],fa[maxn*2],cnt[maxn*2]; inline int read() { char c = getchar(); while (!isalpha(c)) c = getchar(); return c - 'A'; } inline int newn(int x){len[++tot]=x;return tot;} //简化版SAM void sam_ins(int c){ int p=las,np=newn(len[las]+1);las=tot;cnt[np]++; while(p&&!ch[p][c])ch[p][c]=np,p=fa[p]; if(!p)fa[np]=1; else{ int q=ch[p][c]; if(len[q]==len[p]+1) fa[np]=q; else{ int nq=newn(len[p]+1); for(int i=0;i<kind;i++)ch[nq][i]=ch[q][i]; fa[nq]=fa[q]; fa[q]=fa[np]=nq; while(p&&ch[p][c]==q) ch[p][c]=nq,p=fa[p]; } } } int now=1; int ans=1; inline void solve(int v){ if(ch[now][v]){ now=ch[now][v]; } else{ ++ans; now=ch[1][v]; } } int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=0;i<n;i++){ sam_ins(read()); } for(int i=0;i<m;i++){ solve(read()); } printf("%d\n",ans); return 0; }

传送门 TJOI2015弦论 对于一个给定长度为N的字符串，求它的第K小子串是什么。 （位置相同和位置不同的贡献不定） 利用了计数排序的思想，在统计数量时，为了避免漏掉和增多，在统计时候 如果我们计算$sum[fa[i]]+=sum[i]$时，必须保证i已经统计完毕，根据SAM的性质len[fa[i]]小于len[i]，所以可以根据长度排序然后从最长的统计到根节点。

#include<bits/stdc++.h> using namespace std; const int maxn=5e5+150; const int kind=26; int n,t,k,tot=1,las=1; char s[maxn]; int ch[maxn*2][kind]; int len[maxn*2],fa[maxn*2],cnt[maxn*2]; int l,x; int a[maxn*2],who[maxn*2]; int sum[maxn*2]; inline int newn(int x){len[++tot]=x;return tot;} //简化版SAM void sam_ins(int c){ int p=las,np=newn(len[las]+1);las=tot;cnt[np]++; while(p&&!ch[p][c])ch[p][c]=np,p=fa[p]; if(!p)fa[np]=1; else{ int q=ch[p][c]; if(len[q]==len[p]+1) fa[np]=q; else{ int nq=newn(len[p]+1); for(int i=0;i<kind;i++)ch[nq][i]=ch[q][i]; fa[nq]=fa[q]; fa[q]=fa[np]=nq; while(p&&ch[p][c]==q) ch[p][c]=nq,p=fa[p]; } } } void updatecount(){ for(int i=1;i<=tot;i++)a[len[i]]++; for(int i=1;i<=tot;i++)a[i]+=a[i-1]; for(int i=1;i<=tot;i++)who[a[len[i]]--]=i; for(int i=tot;i>=2;i--)cnt[fa[who[i]]]+=cnt[who[i]]; } char ans[maxn]; int main(){ scanf("%s",s+1); int slen=strlen(s+1); scanf("%d%d",&t,&k); for(int i=1;i<=slen;i++)sam_ins(s[i]-'a'); //计数排序 updatecount(); if(t==0) for(int i=2;i<=tot;i++)cnt[i]=1; cnt[1]=0; for(int i=1;i<=tot;i++)sum[i]=cnt[i]; for(int i=tot;i>=1;i--) for(int j=0;j<kind;j++) if(ch[who[i]][j])sum[who[i]]+=sum[ch[who[i]][j]]; int now=1,num=0; while(k){ for(int i=0;i<kind;i++) if(ch[now][i]){ if(k<=sum[ch[now][i]]){ ans[num++]='a'+i; now=ch[now][i]; k-=cnt[now]; break; } else k-=sum[ch[now][i]]; } } if(k) printf("-1\n"); else{ ans[num]=0; printf("%s\n",ans); } return 0; }

SDOI2016生成魔咒 题面 其实就是求SAM新建一个节点的时候，新加了多少个本质不同的子串。 对于新建的一个节点贡献的本质不同的子串数目为 $ans=len[i]-len[fa[i]]$ 新添的字符新建的节点就是last，不过这个题目需要map存边。

#include<bits/stdc++.h> using namespace std; const int maxn=2e5+150; typedef long long ll; int n,tot=1,las=1; map<int,int>ch[maxn]; int len[maxn],fa[maxn]; inline int newn(int x){len[++tot]=x;return tot;} ll ans=0; void sam_ins(int c){ int p=las,np=newn(len[las]+1);las=tot; while(p&&ch[p].find(c)==ch[p].end())ch[p][c]=np,p=fa[p]; if(!p)fa[np]=1; else{ int q=ch[p][c]; if(len[q]==len[p]+1) fa[np]=q; else{ int nq=newn(len[p]+1); ch[nq]=ch[q]; fa[nq]=fa[q]; fa[q]=fa[np]=nq; while(p&&ch[p][c]==q) ch[p][c]=nq,p=fa[p]; } } ans+=len[np]-len[fa[np]]; } int main(){ scanf("%d",&n); int c; for(int i=1;i<=n;i++){ scanf("%d",&c); sam_ins(c); printf("%lld\n",ans); } return 0; }

HAOI2016找相同字符 给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。 简单的广义SAM dfs染色可以求本质不同的子串 但是这个题目要求是位置不同的贡献多个，而且只有两个串，所以方法蛮多的。 第一种： 先把第一个串扔进SAM然后统计一个数组 $sum[i]=sum[fa[i]]+cnt[i]\ast (len[i]-len[fa[i]])$ 这个数组表示的是这个点以及其祖先节点，共出现了多少个子串（非本质不同）。 在统计cnt[i]（一个节点出现的次数）时，我们需要先将所有的孙子节点统计完在统计祖先节点，即从底向上。 而统计sum恰恰相反，要从上向下。 这样我们在跑第二个串的时候，跑到一个匹配的节点，那肯定它的祖先节点可以匹配，并且我们可以维护匹配的长度l，(l-len[i])*cnt就是当前状态节点贡献的子串的数目。

#include<bits/stdc++.h> using namespace std; const int maxn=2e5+150; const int kind=26; typedef long long ll; int tot=1,las=1; int ch[maxn*2][kind]; int len[maxn*2],fa[maxn*2],cnt[maxn*2]; char s1[maxn],s2[maxn]; int vis[maxn*2]; int a[maxn*2],who[maxn*2]; ll sum[maxn*2]; inline int newn(int x){len[++tot]=x;return tot;} void sam_ins(int c){ int p=las,np=newn(len[las]+1);las=tot;cnt[np]++; while(p&&!ch[p][c])ch[p][c]=np,p=fa[p]; if(!p)fa[np]=1; else{ int q=ch[p][c]; if(len[q]==len[p]+1) fa[np]=q; else{ int nq=newn(len[p]+1); for(int i=0;i<kind;i++)ch[nq][i]=ch[q][i]; fa[nq]=fa[q]; fa[q]=fa[np]=nq; while(p&&ch[p][c]==q) ch[p][c]=nq,p=fa[p]; } } } void updatecout(){ for(int i=1;i<=tot;i++)a[len[i]]++; for(int i=1;i<=tot;i++)a[i]+=a[i-1]; for(int i=1;i<=tot;i++)who[a[len[i]]--]=i; for(int i=tot;i>=2;i--)cnt[fa[who[i]]]+=cnt[who[i]]; for(int i=1;i<=tot;i++)sum[who[i]]=sum[fa[who[i]]]+1ll*cnt[who[i]]*(len[who[i]]-len[fa[who[i]]]); } int main(){ scanf("%s",s1); scanf("%s",s2); int l1=strlen(s1); for(int i=0;i<l1;i++) sam_ins(s1[i]-'a'); updatecout(); int now=1; int l=0; int l2=strlen(s2); ll ans=0; for(int i=0;i<l2;i++){ int x=s2[i]-'a'; if(ch[now][x]){ ++l; now=ch[now][x]; }else{ while(now&&!ch[now][x])now=fa[now]; if(now)l=len[now]+1,now=ch[now][x]; else now=1,l=0; } ans+=sum[fa[now]]+1ll*cnt[now]*(l-len[fa[now]]);//(小心爆int) } printf("%lld\n",ans); return 0; }

第二种: 广义SAM 这里有很多需要注意的地方 首先我们在把las定为1，然后再输入新串，这个时候申请的np节点可能会是重复的 感受一下{ab,abc}这种

void sam_ins(int c){ int p=las,np=newn(len[las]+1);las=tot;cnt[np]++; while(p&&!ch[p][c])ch[p][c]=np,p=fa[p]; if(!p)fa[np]=1; else{ int q=ch[p][c]; if(len[q]==len[p]+1) fa[np]=q; else{ int nq=newn(len[p]+1); for(int i=0;i<kind;i++)ch[nq][i]=ch[q][i]; fa[nq]=fa[q]; fa[q]=fa[np]=nq; while(p&&ch[p][c]==q) ch[p][c]=nq,p=fa[p]; } } }

这时候会有节点表示完全相同的东西 len[fa[i]]==len[i]如果直接进行基数排序会wa SAM能直接基数排序代表拓扑序 成立的条件是 len[i]严格大于len[fa[i]]所以我们需要讨论一下 看看是不是需要新建节点。 先看代码：

inline int newn(int x){len[++tot]=x;return tot;} void sam_ins(int c){ int p=las; //主要是这一段 if(ch[p][c]){ int q=ch[p][c]; //判断的条件和申请np其实是一样的。注意更新las的值就行 if (len[q]==len[p]+1){ las=q; return; } int nq=newn(len[p]+1); for(int i=0;i<kind;i++)ch[nq][i]=ch[q][i]; fa[nq]=fa[q]; fa[q]=nq; while(p&&ch[p][c]==q) ch[p][c]=nq,p=fa[p]; las=nq; return; } int np=newn(len[las]+1);las=tot;cnt[np]++; while(p&&!ch[p][c])ch[p][c]=np,p=fa[p]; if(!p)fa[np]=1; else{ int q=ch[p][c]; if(len[q]==len[p]+1) fa[np]=q; else{ int nq=newn(len[p]+1); for(int i=0;i<kind;i++)ch[nq][i]=ch[q][i]; fa[nq]=fa[q]; fa[q]=fa[np]=nq; while(p&&ch[p][c]==q) ch[p][c]=nq,p=fa[p]; } } }

我们在判断出是否新建np的时候其实和原版SAM申请nq的时候是一样的。注意更新las.代码这样很臃肿 所以我们可以整理一下。完整的代码如下

#include<bits/stdc++.h> using namespace std; const int maxn=5e5+150; const int kind=26; typedef long long ll; int tot=1,las=1; int ch[maxn*2][kind]; int len[maxn*2],fa[maxn*2],cnt[maxn*2]; char s1[maxn],s2[maxn]; int vis[maxn*2]; int a[maxn*2],who[maxn*2]; ll sum[maxn*2]; int d1[maxn*2],d2[maxn*2]; inline int newn(int x){len[++tot]=x;return tot;} inline int newnq(int p,int w){ int nq=newn(len[p]+1); int q=ch[p][w]; for(int i=0;i<kind;i++)ch[nq][i]=ch[q][i]; fa[nq]=fa[q]; fa[q]=nq; while(p&&ch[p][w]==q)ch[p][w]=nq,p=fa[p]; return nq; } void sam_ins(int c){ int p=las; if(ch[p][c]){ int q=ch[p][c]; if (len[q]==len[p]+1)las=q; else las=newnq(p,c); return ; } int np=newn(len[las]+1);las=tot;cnt[np]++; while(p&&!ch[p][c])ch[p][c]=np,p=fa[p]; if(!p)fa[np]=1; else{ int q=ch[p][c]; if(len[q]==len[p]+1) fa[np]=q; else{ fa[np]=newnq(p,c); } } } void updatecout(){ for(int i=1;i<=tot;i++)a[len[i]]++; for(int i=1;i<=tot;i++)a[i]+=a[i-1]; for(int i=1;i<=tot;i++)who[a[len[i]]--]=i; for(int i=tot;i;i--)d1[fa[who[i]]]+=d1[who[i]],d2[fa[who[i]]]+=d2[who[i]]; } int main(){ scanf("%s",s1); scanf("%s",s2); int l1=strlen(s1); for(int i=0;i<l1;i++) sam_ins(s1[i]-'a'),d1[las]++; las=1; int l2=strlen(s2); for(int i=0;i<l2;i++) sam_ins(s2[i]-'a'),d2[las]++; updatecout(); ll ans=0; for(int i=1;i<=tot;i++) ans+=1ll*(len[i]-len[fa[i]])*d1[i]*d2[i]; printf("%lld\n",ans); return 0; }