来自蒟蒻XXJ的做题记录

题解可以去看看wjmzbmr的ppt

在这里记录几个问题：

1.居然在extend的过程中忘记了==要更新lth

2.居然直接用了儿子匹配到的长度去更新父亲==

3.按照lth进行排序就可以出来一个天然的按照先儿子后父亲的顺序排好的序列。

代码：

#include
    
     #define mem(i,j) memset(i,j,sizeof(i))#define mcy(i,j) memcpy(i,j,sizeof(i))using namespace std;const int MAXN=200010;const int INF=1008610086;int n;void hello(){    freopen("a.in","r",stdin);    freopen("a.ans","w",stdout);}struct SAM{    int trans[MAXN][26],lth[MAXN],fa[MAXN];    int last,cnt;    int mp[MAXN],mx[MAXN];    SAM(){        cnt=0;last=++cnt;        mem(trans,0);mem(fa,0);        for(int i=1;i
     
      sam.lth[j];}void input(){    scanf("%s",c);    sam.build(c);    for(int i=1;i<=sam.cnt;i++) rank[i]=i;    sort(rank+1,rank+sam.cnt+1,cmp);}void xxj(){    while(scanf("%s",c)==1){        int len=strlen(c),ans(0),p=1;        for(int i=0;i
      
       sam.mx[index]) sam.mp[index]=sam.mx[index];            if(!sam.fa[index]) continue;            if(sam.mx[index]) sam.mx[sam.fa[index]]=sam.lth[sam.fa[index]];        }        mem(sam.mx,0);    }}void output(){    int ans(0);    for(int i=1;i<=sam.cnt;++i){        if(sam.mp[i]==INF) continue;        ans=max(ans,sam.mp[i]);    }    cout<
       
        <