沙茶博主在抢救之前的字符串水平：KMP+Manacher+哈希+(不熟的)AC自动机

所以自我抢救系列又多了一篇

(这人怎么什么都要抢救，回炉重造吧）

表示12月集训后只学会了怎么写SAM，完全不知道怎么用

断断续续到了省选前三周，再不学就不用学了=。=

所以这篇文章同样不适合用来学SAM

(主要是抢救SAM，如果还有空就再看看AC自动机

(废话结束)

(个人意见：SAM比SA好写好调好理解，表示完全不知道SA在干什么)

(如果一定要我求SA？往下看)

(当然只是沙茶博主的个人意见)

---

SAM那一套理论.jpg

right集合，parent树，trans边，maxlen的基本定义就不说了(当然大家叫法都不一样)

广义SAM：每次插完一个串lst指回根节点重新插

关于right集合

建出parent树之后DFS一遍得到每个节点的子树大小就是每个节点的right集合的大小，从下往上right集合的大小变大(废话

关于parent树

一个点的父亲代表的状态是这个点代表的状态的后缀

关于trans边

按着trans边从下往上统计size，得到的每个节点的大小就是以它开始的子串数目

如果按照right的大小来得到的是本质相同算多个的，直接做得到的是本质不同的

关于maxlen

每个状态$s$代表的长度区间是$([len[fth[s]],len[s])$，从下往上len变小(废话

好的这些东西看看就好，更有用的在下面

哦对了，所谓的“(把某个串)放到SAM上跑”就是说从根节点出发有当前字符的trans边就走，没有就跳parent树直到有了再走一次(或者一直没有回到了根节点)

---

具体应用

①求本质不同子串数目

所有节点的$\sum len[i]-len[fth[i]]$

例题1

标记一下两个串来区分，然后乘法原理统计

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 const int N=800005; 6 int p[N],noww[N],goal[N]; 7 int trs[N][26],fth[N],len[N],siz[N][2]; 8 int l1,l2,cnt,tot,lst; long long ans; char s1[N],s2[N]; 9 void Link(int f,int t)10 {11     noww[++cnt]=p[f];12     goal[cnt]=t,p[f]=cnt;13 }14 void Insert(int ch,int tp)15 {16     int nde=lst,newn=++tot; lst=newn;17     siz[newn][tp]=1,len[newn]=len[nde]+1;18     while(nde&&!trs[nde][ch])19         trs[nde][ch]=newn,nde=fth[nde];20     if(!nde) fth[newn]=1;21     else 22     {23         int tran=trs[nde][ch];24         if(len[tran]==len[nde]+1)25             fth[newn]=tran;26         else 27         {28             int rnde=++tot; len[rnde]=len[nde]+1;29             for(int i=0;i<=25;i++) trs[rnde][i]=trs[tran][i];30             fth[rnde]=fth[tran],fth[tran]=fth[newn]=rnde;31             while(nde&&trs[nde][ch]==tran)32                 trs[nde][ch]=rnde,nde=fth[nde];33         }34     }35 }36 void DFS(int nde)37 {38     for(int i=p[nde],g;i;i=noww[i])39     {40         DFS(g=goal[i]);41         siz[nde][0]+=siz[g][0];42         siz[nde][1]+=siz[g][1];43     }44     ans+=1ll*(len[nde]-len[fth[nde]])*siz[nde][0]*siz[nde][1];45 }46 int main()47 {48     register int i;49     scanf("%s%s",s1+1,s2+1);50     l1=strlen(s1+1),l2=strlen(s2+1),lst=tot=1;51     for(i=1;i<=l1;i++) Insert(s1[i]-'a',0); lst=1;52     for(i=1;i<=l2;i++) Insert(s2[i]-'a',1);53     for(i=1;i<=tot;i++) Link(fth[i],i);54      DFS(1),printf("%lld",ans);55     return 0;56 }
        
       
      

例题2 

同样还是标记每个串，只有子树里都一样才统计

1 #include

例题3

广义SAM也一样做，这题从每个叶子开始跑一次DFS插进去就好了

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 const int N=4000005; 6 int trs[N][10],fth[N],len[N],siz[N]; 7 int p[N],noww[N],goal[N],deg[N],col[N]; 8 int n,k,t1,t2,cnt,tot; long long ans;  9 void Link(int f,int t)10 {11     noww[++cnt]=p[f],p[f]=cnt;12     goal[cnt]=t,deg[t]++;13     noww[++cnt]=p[t],p[t]=cnt;14     goal[cnt]=f,deg[f]++;15 }16 int Insert(int ch,int lst)17 {18     int nde=lst,newn=++tot; 19     lst=newn,len[newn]=len[nde]+1;20     while(nde&&!trs[nde][ch])21         trs[nde][ch]=newn,nde=fth[nde];22     if(!nde) fth[newn]=1;23     else 24     {25         int tran=trs[nde][ch];26         if(len[tran]==len[nde]+1)27             fth[newn]=tran;28         else 29         {30             int rnde=++tot; len[rnde]=len[nde]+1;31             for(int i=0;i<=9;i++) trs[rnde][i]=trs[tran][i];32             fth[rnde]=fth[tran],fth[tran]=fth[newn]=rnde;33             while(nde&&trs[nde][ch]==tran)34                 trs[nde][ch]=rnde,nde=fth[nde];35         }36     }37     return newn;38 }39 void DFS(int nde,int fth,int lst)40 {41     lst=Insert(col[nde],lst);42     for(int i=p[nde];i;i=noww[i])43         if(goal[i]!=fth) DFS(goal[i],nde,lst);44 }45 int main()46 {47     register int i;48     scanf("%d%d",&n,&k),tot=1;49     for(i=1;i<=n;i++) scanf("%d",&col[i]);50     for(i=1;i
        
       
      

ex① 多次区间询问

利用zrq讲的那个

②两个串的最长公共子串

一个建SAM一个放上去跑，走一次trans长度加1，跳parent将长度同步为当前节点的len

ex② 多个串

并没有什么变化，每个串都跑一遍，在每个节点都将答案取min

例题

1 #include

③第k小子串

上面已经说了怎么统计以每个节点开始的本质相同算多个/一个的子串数目，求第k小就从根节点沿着trans往下走，每次扣掉对应的大小

(我还想怎么求第$k$大子串，后来发现第$k$小子串都能求了不会求第$k$大是不是有点沙茶啊=。=)

④最小表示法

把串插两遍，然后从根节点开始沿着字典序最小的trans走，记录走过的字符

例题 洛谷 1368 工艺

然而你可以看到SAM跑的非常惨，因为依赖map多一个log，而且空间也是四倍的

1 #include

⑤子串的出现次数

记录右端点对应的parent树节点，在倍增跳parent树跳到最靠上的len小于等于该串长度的节点，该节点的siz就是子串出现的次数

例题 APIO 2014 回文串

本质不同的回文串只有$O(n)$级别，所以manacher+SAM就好了

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 const int N=600060,K=20; 6  7 int p[N],noww[N],goal[N]; 8 int rnk[N],bkt[N],mul[N][K]; 9 int trs[N][26],fth[N],len[N],siz[N],num[N];10 char str[N>>1],Str[N]; 11 int lth,lst,cnt,tot,mid,maxr;12 long long ans;13 14 void link(int f,int t)15 {16     noww[++cnt]=p[f];17     goal[cnt]=t,p[f]=cnt;18 }19 20 void DFS(int nde,int fth)21 {22     mul[nde][0]=fth;23     for(int i=p[nde];i;i=noww[i]) 24         DFS(goal[i],nde),siz[nde]+=siz[goal[i]];25     for(int i=1;mul[nde][i];i++)26         mul[nde][i]=mul[mul[nde][i-1]][i-1];27 }28 void Insert(int ch,int ps)29 {30     int nde=lst,newn=++tot; 31     num[ps]=lst=newn,siz[newn]=1,len[newn]=len[nde]+1;32     while(nde&&!trs[nde][ch])33         trs[nde][ch]=newn,nde=fth[nde];34     if(!nde) fth[newn]=1;35     else36     {37         int tran=trs[nde][ch];38         if(len[tran]==len[nde]+1)39             fth[newn]=tran;40         else41         {42             int rnde=++tot; len[rnde]=len[nde]+1;43             for(int i=0;i<=25;i++) trs[rnde][i]=trs[tran][i];44             fth[rnde]=fth[tran],fth[tran]=fth[newn]=rnde;45             while(nde&&trs[nde][ch]==tran)46                 trs[nde][ch]=rnde,nde=fth[nde];47         }48     }49 }50 void prework()51 {52     register int i,j;53     scanf("%s",str+1),lth=strlen(str+1),lst=tot=1;54     for(i=1;i<=lth;i++) Insert(str[i]-'a',i);55     for(i=1;i<=tot;i++) link(fth[i],i); DFS(1,0);56 }57 void Solve(int l,int r)58 {59     l=(l+l%2)/2,r=(r-r%2)/2; 60     if(l>r) return ;61     int nde=num[r],lth=r-l+1;62     for(int i=19;~i;i--)63         if(lth<=len[mul[nde][i]])64             nde=mul[nde][i];65     ans=max(ans,1ll*lth*siz[nde]);66 }67 void Manacher()68 {69     register int i;70     int newl=2*lth+1;71     for(i=1;i<=newl;i++)72         Str[i]=(i&1)?'?':str[i>>1];73     Str[0]='>',Str[newl+1]='<';74     for(i=1;i<=newl;i++)75     {76         fth[i]=(maxr>=i)?min(maxr-i+1,fth[2*mid-i]):1;77         Solve(i-fth[i]+1,i+fth[i]-1);78         while(Str[i-fth[i]]==Str[i+fth[i]]) 79             fth[i]++,Solve(i-fth[i]+1,i+fth[i]-1);80         if(i+fth[i]-1>maxr) maxr=i+fth[i]-1,mid=i;81     }82 }83 int main()84 {85     prework(),Manacher();86     printf("%lld",ans);87     return 0;88 }
        
       
      

⑥两个P(refix)的LCS(uffix)

两个P的LCS就是他们parent树上对应节点的LCA，同理的，想要找S的LCP把串反过来插进去即可

一个事实是所有位置对所代表的的P的LCS之和等于所有位置对所代表的S的LCP之和

例题

通过上面那个东西转变成parent树上两两路径之和，统计每条边的贡献即可

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 const int N=1000005; 6 int p[N],noww[N],goal[N]; 7 int trs[N][26],fth[N],len[N],siz[N]; 8 int lth,cnt,tot,lst; long long ans; char str[N]; 9 void Link(int f,int t)10 {11     noww[++cnt]=p[f];12     goal[cnt]=t,p[f]=cnt;13 }14 void Insert(int ch)15 {16     int nde=lst,newn=++tot; lst=newn;17     siz[newn]=1,len[newn]=len[nde]+1;18     while(nde&&!trs[nde][ch])19         trs[nde][ch]=newn,nde=fth[nde];20     if(!nde) fth[newn]=1;21     else 22     {23         int tran=trs[nde][ch];24         if(len[tran]==len[nde]+1)25             fth[newn]=tran;26         else 27         {28             int rnde=++tot; len[rnde]=len[nde]+1;29             for(int i=0;i<=25;i++) trs[rnde][i]=trs[tran][i];30             fth[rnde]=fth[tran],fth[tran]=fth[newn]=rnde;31             while(nde&&trs[nde][ch]==tran)32                 trs[nde][ch]=rnde,nde=fth[nde];33         }34     }35 }36 void DFS(int nde)37 {38     for(int i=p[nde],g;i;i=noww[i])39         DFS(g=goal[i]),siz[nde]+=siz[g];40     for(int i=p[nde],g;i;i=noww[i])41         g=goal[i],ans+=1ll*(len[g]-len[nde])*(lth-siz[g])*siz[g];42 }43 int main()44 {45     register int i;46     scanf("%s",str+1);47     lth=strlen(str+1),lst=tot=1;48     for(i=lth;i;i--) Insert(str[i]-'a'); 49     for(i=1;i<=tot;i++) Link(fth[i],i);50      DFS(1),printf("%lld",ans);51     return 0;52 }
        
       
      

类似的  

树上DFS一遍求最小值和最大值(记录最小值是因为可能两个负数乘起来更大)，思路是不是非常清新啊(踩踩后缀数组

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 const int N=600005; 6 const long long inf=1e18; 7 int lth,cnt,tot,lst; char str[N]; 8 int p[N],noww[N],goal[N],trs[N][26],fth[N],len[N],siz[N]; 9 long long del[N],mini[N],maxi[N],mem1[N],mem2[N],ans1[N],ans2[N];10 void Maxi(long long &x,long long y){
    if(x
         
          y) x=y;}12 void Link(int f,int t)13 {14     noww[++cnt]=p[f];15     goal[cnt]=t,p[f]=cnt;16 }17 int Insert(int ch)18 {19     int nde=lst,newn=++tot; lst=newn;20     siz[newn]=1,len[newn]=len[nde]+1;21     while(nde&&!trs[nde][ch])22         trs[nde][ch]=newn,nde=fth[nde];23     if(!nde) fth[newn]=1;24     else 25     {26         int tran=trs[nde][ch];27         if(len[tran]==len[nde]+1)28             fth[newn]=tran;29         else 30         {31             int rnde=++tot; len[rnde]=len[nde]+1;32             for(int i=0;i<=25;i++) trs[rnde][i]=trs[tran][i];33             fth[rnde]=fth[tran],fth[tran]=fth[newn]=rnde;34             while(nde&&trs[nde][ch]==tran)35                 trs[nde][ch]=rnde,nde=fth[nde];36         }37     }38     return newn;39 }40 void DFS(int nde)41 {42     for(int i=p[nde],g;i;i=noww[i])43     {44         DFS(g=goal[i]);45         mem1[nde]+=1ll*siz[nde]*siz[g],siz[nde]+=siz[g];46         if(mini[nde]!=inf) Maxi(mem2[nde],mini[nde]*mini[g]);47         if(maxi[nde]!=-inf) Maxi(mem2[nde],maxi[nde]*maxi[g]);48         Maxi(maxi[nde],maxi[g]),Mini(mini[nde],mini[g]);49     }50 }51 void Init()52 {53     lst=tot=1;54     for(int i=1;i<=2*lth;i++)55         mini[i]=inf,maxi[i]=mem2[i]=ans2[i]=-inf;56 }57 int main()58 {59     register int i;60     scanf("%d%s",&lth,str+1),Init();61     for(i=1;i<=lth;i++) scanf("%lld",&del[i]);62     for(i=lth;i;i--) 63     {64         int nde=Insert(str[i]-'a');65         maxi[nde]=mini[nde]=del[i];66     }67     for(i=1;i<=tot;i++) Link(fth[i],i); DFS(1);68     for(i=1;i<=tot;i++) 69     {70         ans1[len[i]]+=mem1[i];71         Maxi(ans2[len[i]],mem2[i]);72     }73     for(i=lth-2;~i;i--) ans1[i]+=ans1[i+1],Maxi(ans2[i],ans2[i+1]);74     for(i=0;i
         
        
       
      

ex⑥ 多次询问一些P/S两两的LCS/LCP之和

在parent树上建虚树之后DP

⑦求一个字符串中只出现了一次的所有子串

这些子串对应的状态都是parent树里的叶子，对每个状态记录它对应的任意一个子串的结束位置endp，每个只出现一次的串就对应$[endp-len+1,endp]$这个区间

⑧两个字符串a,b，多次询问a的一个区间$[l,r]$在b上出现了多少次

对b建SAM，把a放上去跑，记录每个右端点最长匹配长度和对应的节点。对于每个询问如果右端点对应的匹配长度不够就没出现，够就变成⑤从对应的节点开始跳

⑨给出一坨字符串$a[]$和一个字符串b，每次询问b的一个子串在$a[]$的一段字符串$a[l]......a[r]$中哪个出现次数最大(CF666E)

对$a[]$建广义SAM，每个节点用线段树记录$a[]$中串的出现情况，跑一次线段树合并。然后用⑤的方法定位状态，在对应的线段树上查询

⑩给出一坨字符串，询问每个串有多少子串在至少$k$个串里出现过

建立广义SAM，每个节点用set记录这个状态被哪些串包含。把每个串放在SAM上跑，当匹配的点出现次数小于k时跳parent树直到次数不小于k，将对应的len计入答案

 

套路有一些，还有就是反复倒腾SAM的性质和一些基本的操作

 

最后还有一个问题，如果一定要我求SA怎么办呢？

SAM也能求！按说是$O(n)$的，然而因为一般空间开不下所以只能用map=。=

对反串建SAM，记录每个节点是不是后缀，按trans跑拓扑排序后建树(不是parent树)DFS一遍，具体看代码

UOJ 模板 后缀排序(因为常数太大惨遭后缀排序吊打)

1 #include