SP10570

标签：rnk int SP10570 maxm Len prnk sa

后缀数组做法。

用不同的分隔字符将 \(n\) 个串连接起来， 如 \(\texttt{abcdefg}\) 、 \(\texttt{qaq}\) 、 \(\texttt{qwq}\) 拼成 \(\texttt{abcdefgAqaqBqwqC}\)。

求出新串的后缀数组和 height 数组，然后二分答案，问题转变为判断是否有一个长度为 \(p\) 的串在所有的串中出现，判断方法是扫描整个 height 数组，将它分为若干个段，每个段的最初 \(p\) 个字符均相同，如果该段包含的所有串，那么 \(p\) 就是满足条件的。

#include <bits/stdc++.h>
#define _for(I,A,B) for(int I=(A); I<=(B); I++)
#define _rof(I,A,B) for(int I=(A); i>=(B); I--)
using namespace std;
const int N=4e5+11;
int sa[N], height[N], rnk[N];
struct Suffix_Array{
  int prnk[N], y[N], c[N];
  bool issame(int x, int y, int w){
    return prnk[x]==prnk[y]&&prnk[x+w]==prnk[y+w];
  }
  void solve(char *A, int Len){
    _for(i,0,Len+111) sa[i]=height[i]=rnk[i]=prnk[i]=0;
    int m=300, maxm=300;
    _for(i,0,maxm+11) c[i]=0;
    _for(i,1,Len) c[rnk[i]=A[i]]++;
    _for(i,1,maxm) c[i]+=c[i-1];
    _rof(i,Len,1) sa[c[rnk[i]]--]=i;
    for(int w=1; w<=Len; w<<=1,maxm=m){
      m=0;
      _for(i,Len-w+1,Len) y[++m]=i;
      _for(i,1,Len) if(sa[i]>w) y[++m]=sa[i]-w;
      _for(i,1,maxm+11)c[i]=0;
      _for(i,1,Len) c[rnk[y[i]]]++;
      _for(i,1,maxm) c[i]+=c[i-1];
      _rof(i,Len,1) sa[c[rnk[y[i]]]--]=y[i];
      memcpy(prnk,rnk,sizeof(int)*(Len+9)),m=0;
      _for(i,1,Len) rnk[sa[i]]=issame(sa[i],sa[i-1],w)?m:++m;
      if(m==Len)break;
    }
    for(int i=1, k=0, j; i<=Len; i++){
      if(k)k--;
      j=sa[rnk[i]-1];
      while(A[i+k]==A[j+k])k++;
      height[rnk[i]]=k;
    }
  }
}SA;
char s[N<<3], buf[N];
int n, slen, id[N], MAX, idcnt, flag[N];
bool check(int l, int r){
  int CNT=0; idcnt++;
  _for(i,l,r) if(flag[id[sa[i]]]!=idcnt&&id[sa[i]]!=0)
    flag[id[sa[i]]]=idcnt, CNT++;
  return CNT>=n;
}
bool checker(int Length){
  for(int L=1, R=2; R<=slen+1; R++){
    if(height[R]<Length||R==slen+1){
      if(check(L,R-1))return 1;
      L=R;
    }
  }
  return 0;
}
void sol(){
  scanf("%d", &n), slen=0, MAX=1145141;
  _for(i,1,n){
    scanf(" %s", buf);
    int buflen=strlen(buf);
    MAX=min(MAX, buflen);
    _for(j,0,buflen-1) s[++slen]=buf[j], id[slen]=i;
    s[++slen]='A'+i-1, id[slen]=0;
  }
  s[slen+1]=s[slen+2]='\0';
  id[slen+1]=id[slen+2]=0;
  SA.solve(s, slen);
  int ans=0, l=0, r=MAX;
  while(l<=r){
    int mid=l+r>>1;
    if(checker(mid))ans=mid,l=mid+1;
    else r=mid-1;
  }
  printf("%d\n", ans);
}
int main(){
  #ifdef B
    freopen("text.in","r",stdin);
    freopen("text.out","w",stdout);
  #endif
  int T; scanf("%d", &T);
  while(T--) sol();
  return 0;
}

标签：rnk,int,SP10570,maxm,Len,prnk,sa
From： https://www.cnblogs.com/dadidididi/p/17353510.html