2019.4.11 一题 XSY 1551 ——广义后缀数组（trie上后缀数组）

时间：2023-03-10 06:56:23
2019.4.11 一题 XSY 1551 ——广义后缀数组（trie上后缀数组）

2019.4.11 一题 XSY 1551 ——广义后缀数组（trie上后缀数组）

2019.4.11 一题 XSY 1551 ——广义后缀数组（trie上后缀数组）

参考：http://www.mamicode.com/info-detail-1949898.html （log2）

　　　https://blog.****.net/geotcbrl/article/details/50907662

　　　https://blog.****.net/cdsszjj/article/details/79920308

　　　https://blog.****.net/ez_yww/article/details/77072632

trie 上后缀数组想做的是把 trie 树每个节点开始到根的字符串排好序，求出 rk[ ] 和 sa[ ] ，需要的话也可以求出 ht[ ]。

普通后缀数组比较大小是通过倍增，即 [ i , i+k-1 ] 和 [ i+k , i+2k-1 ] 这两个位置作为两个关键字得到 [ i , i+2k-1 ] 的排名。这里也一样。

在树上的话， i+k 变成 i 点往上第 k 个祖先；所以先处理好祖先的倍增数组；顺便作出 dep[ ] ；

希望把每个 2t 时刻的 rk 数组存下来，所以令 rk[ t ][ i ] 表示第 t 次比较的时候 i 的排名。

当前这次比较的时候，tp[ ] 里要存按第二关键字排好序的序列，即 tp[ i ] 表示 “ 2t-1 次祖先排名为 i 的节点是谁 ” ；这里的 “排名为 i ” 指的是 “向上 2t-1 范围的字符串” 排名，即 rk[ t-1 ][ i ] 。

所以现在已知上一次的 sa 和 rk ，希望做出 tp[ ] 。只要记录一下每个点的 2t-1 次后代有些谁（注意可能有多个点），然后像平常一样把没有 2t-1 次祖先的点填在最前面，再按 sa 枚举，tp[ ++tot ] = 后代 即可。

原来用 vector 存了这些后代。但非常慢。每次通过 pre[ i ][ t-1 ] 连一个临接表出来会快很多。

然后希望作出 ht 。先要作出 ht[ i ][ 0 ] 。

现在真实的排名是最后一次做出的那个 rk 。所以 ht 是基于最后一次的 rk 和 sa 上求的。保留之前的 rk 可以用来求相邻两个字符串的 LCP 。就是像倍增一样。如果 rk[ t ][ x ] == rk[ t ][ y ] ，说明 i 和 j 向上 2t 个字符都是一样的，那么 ret+= bin[ t ] , x = pre[ x ][ t ] , y = pre[ y ][ t ] 。

当然也可以不保留这些 rk ，倍增地存一下每个点往上的哈希值也行。（所以比较两个串的复杂度是 log 而不是 log2 的！“二分” 和 “提取哈希值” 可以一起做！）

（这样有一个做法，就是启发式合并，合并子树的时候把小的部分的字符串二分地插入大的部分的字符串集合中。但支持 “提取某位置的元素” 和 “插入” 的数据结构会带 log ，所以是 log3 ，真遗憾）

注意桶要包含 0 位置。因为根向上没有字符，初始 rk 是 0 。同时注意输入的边上字符有 0 ，所以把输入都 +1 ，体现 “没有” 比 0 大。

然后这道题再套一个线段树合并就行了。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<set>

#define ll long long

using namespace std;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

int Mx(int a,int b){return a>b?a:b;}

int Mn(int a,int b){return a<b?a:b;}

const int N=2e5+,K=,bs=,md=1e9+;

int n,dep[N],hs[N][K+],pre[N][K],lj[N];

int sa[N],rk[N],ht[N][K+],bin[K+],lg[N];

int hd[N],xnt,to[N],nxt[N],rt[N],ans;

struct Node{

  int x;

  Node(int x=):x(x) {}

  bool operator< (const Node &b)const

  {return rk[x]<rk[b.x];}

};

set<Node> st[N];

set<Node>::iterator it,it2;

int get_lcp(int u,int v)

{

  int ret=;

  for(int t=lg[Mn(dep[u],dep[v])];t>=;t--)//Mn not Mx

    if(pre[u][t]&&pre[v][t]&&hs[u][t]==hs[v][t])//if pre[][]

      u=pre[u][t], v=pre[v][t], ret+=bin[t];

  return ret;

}

bool cmp(int u,int v)

{

  for(int t=lg[Mn(dep[u],dep[v])];t>=;t--)//Mn

    if(pre[u][t]&&pre[v][t]&&hs[u][t]==hs[v][t])//pre[][]

      u=pre[u][t], v=pre[v][t];

  return hs[u][]<hs[v][];

}

void get_ht()

{

  for(int i=;i<=n;i++)

    ht[i][]=get_lcp(sa[i-],sa[i]);

  for(int t=;t<=lg[n];t++)

    for(int i=;i+bin[t]-<=n;i++)

      ht[i][t]=Mn(ht[i][t-],ht[i+bin[t-]][t-]);

}

int qry_ht(int u,int v)

{

  if(u==v)return dep[u];

  u=rk[u]; v=rk[v]; if(u>v)swap(u,v);

  u++; int d=lg[v-u+];

  return Mn(ht[u][d],ht[v-bin[d]+][d]);

}

int mrg(int &u,int v)

{

  int ret=;

  if(st[u].size()<st[v].size())swap(u,v);

  for(it=st[v].begin();it!=st[v].end();it++)

    {

      st[u].insert(*it);

      it2=st[u].find(*it);

      if(it2!=st[u].begin())

    {

      it2--; ret=Mx(ret,qry_ht((*it2).x,(*it).x));

      it2++;

    }

      it2++; if(it2==st[u].end())continue;

      ret=Mx(ret,qry_ht((*it2).x,(*it).x));

    }

  return ret;

}

void dfs(int cr)

{

  rt[cr]=cr; st[rt[cr]].insert(Node(cr));

  int ret=;

  for(int i=hd[cr],v;i;i=nxt[i])

    {

      dfs(v=to[i]);

      ret=Mx(ret,mrg(rt[cr],rt[v]));

    }

  if(st[rt[cr]].size()>)//if!!!

    {

      ans=Mx(ans,dep[cr]+ret);

    }

}

int main()

{

  freopen("recollection.in","r",stdin);

  freopen("recollection.out","w",stdout);

  n=rdn();

  bin[]=;for(int i=;i<=K;i++)bin[i]=bin[i-]<<;

  for(int i=;i<=n;i++)lg[i]=lg[i>>]+;

  lj[]=;for(int i=;i<=n;i++)lj[i]=(ll)lj[i-]*bs%md;

  int he=, tl=;

  for(int i=;i<=n;i++)

    {

      pre[i][]=rdn();hs[i][]=rdn()+;//+1 for cmp empty

      to[++xnt]=i; nxt[xnt]=hd[pre[i][]]; hd[pre[i][]]=xnt;

    }

  for(int i=;i<=n;i++)

    {

      dep[i]=dep[pre[i][]]+;

      for(int t=,d=pre[i][];(d=pre[i][t-]);t++)

    {

      pre[i][t]=pre[d][t-];

      hs[i][t]=((ll)hs[i][t-]*lj[bin[t-]]+hs[d][t-])%md;

    }

    }

  for(int i=;i<=n;i++)sa[i]=i; sort(sa+,sa+n+,cmp);

  for(int i=;i<=n;i++)rk[sa[i]]=i;

  get_ht(); dfs();

  printf("%d\n",ans);

  return ;

}

log^2

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#define ls Ls[cr]

#define rs Rs[cr]

#define pb push_back

using namespace std;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

int Mx(int a,int b){return a>b?a:b;}

int Mn(int a,int b){return a<b?a:b;}

const int N=2e5+,K=,M=N*K;

int n,dep[N],pre[N][K],hd[N],xnt,to[N],nxt[N];

int ht[K][N],rk[K][N],sa[N],tp[N],tx[N],lm,ans;

int bin[K],lg[N],rt[N],Ls[M],Rs[M],fr[M],sc[M],sm[M],tot;

int h2[N],xt2,t2[N],nt2[N];

void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;}

void ad2(int x,int y){t2[++xt2]=y;nt2[xt2]=h2[x];h2[x]=xt2;}

void Rsort(int n,int nm,int t)

{

  for(int i=;i<=nm;i++)tx[i]=;////// 0 !!!! for empty

  for(int i=;i<=n;i++)tx[rk[t][i]]++;

  for(int i=;i<=nm;i++)tx[i]+=tx[i-];

  for(int i=n;i;i--)sa[tx[rk[t][tp[i]]]--]=tp[i];

}

void get_sa(int n,int nm)

{

  for(int i=;i<=n;i++)tp[i]=i;

  Rsort(n,nm,);

  for(int t=;;t++)

    {

      xt2=; memset(h2,,sizeof h2);

      for(int i=;i<=n;i++)

    if(pre[i][t-])ad2(pre[i][t-],i);

      int tot=;

      for(int i=;i<=n;i++)

    if(!pre[i][t-])tp[++tot]=i;

      for(int i=;i<=n;i++)

    for(int j=h2[sa[i]];j;j=nt2[j])

      tp[++tot]=t2[j];

      Rsort(n,nm,t-); rk[t][sa[]]=nm=;

      for(int i=;i<=n;i++)

    {

      int cr=sa[i], u=pre[cr][t-], v=pre[sa[i-]][t-];

      rk[t][cr]=(rk[t-][cr]==rk[t-][sa[i-]]&&rk[t-][u]==rk[t-][v])?nm:++nm;

    }

      lm=t; if(nm==n)break;

    }

}

int get_lcp(int u,int v)

{

  int ret=;

  for(int t=lm;t>=;t--)//t=lm!!

    if(pre[u][t]&&pre[v][t]&&rk[t][u]==rk[t][v])//pre

      u=pre[u][t], v=pre[v][t], ret+=bin[t];

  return ret;

}

void get_ht()

{

  for(int i=;i<=n;i++)ht[][i]=get_lcp(sa[i-],sa[i]);

  for(int t=;t<=lg[n];t++)

    for(int i=;i<=n;i++)

      ht[t][i]=Mn(ht[t-][i],ht[t-][i+bin[t-]]);

}

int qry_ht(int l,int r)

{

  if(l==r)return dep[sa[l]];

  if(l>r)swap(l,r); l++; int d=lg[r-l+];

  int ret=Mn(ht[d][l],ht[d][r-bin[d]+]);

  return ret;

}

void build(int l,int r,int &cr,int p)

{

  cr=++tot; fr[cr]=sc[cr]=p;

  if(l==r)return; int mid=l+r>>;

  if(p<=mid)build(l,mid,ls,p);

  else build(mid+,r,rs,p);

}

void mrg(int l,int r,int &cr,int pr)

{

  if(!cr){cr=pr;return;} if(!pr)return;

  int mid=l+r>>;

  mrg(l,mid,ls,Ls[pr]); mrg(mid+,r,rs,Rs[pr]);

  fr[cr]=(ls?fr[ls]:fr[rs]); sc[cr]=(rs?sc[rs]:sc[ls]);

  sm[cr]=Mx(sm[ls],sm[rs]);

  if(fr[ls]&&fr[rs])

    sm[cr]=Mx(sm[cr],qry_ht(sc[ls],fr[rs]));

}

void dfs(int cr)

{

  build(,n,rt[cr],rk[lm][cr]);

  for(int i=hd[cr],v;i;i=nxt[i])

    {

      dfs(v=to[i]);

      mrg(,n,rt[cr],rt[v]);

    }

  if(hd[cr])

    {

      ans=Mx(ans,dep[cr]+sm[rt[cr]]);

    }

}

int main()

{

  freopen("recollection.in","r",stdin);

  freopen("recollection.out","w",stdout);

  n=rdn();

  for(int i=;i<=n;i++)lg[i]=lg[i>>]+;

  bin[]=;for(int i=;bin[i-]<=n;i++)bin[i]=bin[i-]<<;

  for(int i=;i<=n;i++)

    {

      int fa=rdn(); rk[][i]=rdn()+;//+1!!!!! for cmp with empty

      dep[i]=dep[fa]+; pre[i][]=fa; add(fa,i);

      for(int t=,d=fa;(d=pre[i][t-]);t++)

    pre[i][t]=pre[d][t-];

    }

  get_sa(n,); get_ht();

  dfs();

  printf("%d\n",ans);

  return ;

}

log