求不同的子串个数

如果规定根的话，那么弯曲的路径难以处理。

由于只有20个叶子，所以以每个叶子分别为根，建20棵trie树，再把20棵trie树合成一棵。

这样，trie上一个到某个祖先的路径构成了所有的子串。（可能重复）

所以trie上建SAM。SAM的路径条数（或者每个点的len[i]-len[fa[i]]）就是本质不同的子串个数

 

至于trie上建SAM，可以dfs，或者bfs建。

只要记录树上x的father的SAM上的节点编号p，从这个p作为nd开始建即可。

#include
      
       #define il inline#define reg register int#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){    char ch;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=100000+5;int n,m;int clo[N];int du[N];struct node{    int nxt,to;}e[2*N];int hd[N],cnt;void add(int x,int y){    e[++cnt].nxt=hd[x];    e[cnt].to=y;    hd[x]=cnt;}struct trie{    int cnt,ch[20*N][10];    trie(){        cnt=1;    }}tr;void dfs(int x,int y,int fa){    if(!tr.ch[y][clo[x]]){        tr.ch[y][clo[x]]=++tr.cnt;    }    y=tr.ch[y][clo[x]];    for(reg i=hd[x];i;i=e[i].nxt){        int z=e[i].to;        if(z==fa) continue;        dfs(z,y,x);    }}struct SAM{    int fa[20*N],len[20*N],ch[20*N][10],cnt;    ll s[20*N];    SAM(){        cnt=1;    }    int ins(int c,int p){        //cout<<" c p "<
       
        <<" "<
        
<
       
      

其实不用建出合并的trie。

直接在20次dfs的时候（每次dfs都是一个小trie），20次每次从根开始插入即可。

重复的前缀部分会和根节点隔离开的。既不会能从根节点到达，而且fa[i]=len[i]，没有包含一个子串。

#include
      
       #define il inline#define reg register int#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){    char ch;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=100010;#define TOT 2000000struct node{    int nxt,to;}e[2*N];int hd[N],cnt;int n,m;int clo[N];void add(int x,int y){    e[++cnt].nxt=hd[x];    e[cnt].to=y;    hd[x]=cnt;}struct SAM{    int fa[TOT],len[TOT],ch[TOT][10],cnt;    ll s[TOT];    SAM(){        cnt=1;    }    int ins(int c,int p){        //cout<<" c p "<
       
        <<" "<
        
<
       
      

 

（当然，如果广义SAM要处理Right集合的大小的话，要根据建造的方法处理

1.所有的串依次从rt=1开始插入

叶子sz赋值为1，然后Parent树上往上push。注意，不管节点是否有实际意义，都要push上去。因为代表一个出现的位置

2.trie树

先要找到trie树某个点的sz[x]，然后插入的时候sz就是这个sz[x]

 

）