BZOJ2946 Poi2000 公共串 【后缀自动机】

Description

   给出几个由小写字母构成的单词，求它们最长的公共子串的长度。

任务：

l 读入单词

l 计算最长公共子串的长度

l 输出结果

Input

文件的第一行是整数 n，1<=n<=5，表示单词的数量。接下来n行每行一个单词，只由小写字母组成，单词的长度至少为1，最大为2000。

Output

仅一行，一个整数，最长公共子串的长度。

Sample Input

3

abcb

bca

acbc

Sample Output

２

---

先对第一个串建后缀自动机

然后把其他的串拿到后缀自动机上面去跑

得到每个节点的最大匹配长度

然后用parent数上子节点的答案更新一下父亲节点的答案

最后把每个串跑出来的结果取min

对每个节点的最后结果取max就可以了

---

#include<bits/stdc++.h>

using namespace std;

#define N 200010

const int CHARSET_SIZE=26;

struct Node{

  int ch[CHARSET_SIZE],prt;

  int maxl;

  Node(int maxl=0):ch(),prt(0),maxl(maxl){}

}t[N];

int root,last,cur;

int topo[N],buc[N];

int newnode(int maxl=0){t[++cur]=Node(maxl);return cur;}

void init(){cur=0;root=last=newnode();}

void extend(int c){

  int u=newnode(t[last].maxl+1),v=last;

  for(;v&&!t[v].ch[c];v=t[v].prt)t[v].ch[c]=u;

  if(!v){t[u].prt=root;}

  else if(t[v].maxl+1==t[t[v].ch[c]].maxl){

    t[u].prt=t[v].ch[c];

  }else{

    int n=newnode(t[v].maxl+1),o=t[v].ch[c];

    memcpy(t[n].ch,t[o].ch,sizeof(t[o].ch));

    t[n].prt=t[o].prt;

    t[o].prt=t[u].prt=n;

    for(;v&&t[v].ch[c]==o;v=t[v].prt)t[v].ch[c]=n;

  }

  last=u;

}

void toposort(){

  int maxv=0;

  for(int p=1;p<=cur;p++){

    maxv=max(maxv,t[p].maxl);

    buc[t[p].maxl]++;

  }

  for(int i=1;i<=maxv;i++)buc[i]+=buc[i-1];

  for(int p=1;p<=cur;p++)topo[buc[t[p].maxl]--]=p;

  fill(buc,buc+maxv+1,0);

}

char c[N];

int ans[N],pic[N];

int main(){

  init();

  int n;scanf("%d",&n); n--;

  scanf("%s",c+1);

  int len=strlen(c+1);

  for(int i=1;i<=len;i++)extend(c[i]-'a');

  toposort();

  for(int i=1;i<=cur;i++)ans[i]=t[i].maxl;

  while(n--){

    for(int i=1;i<=cur;i++)pic[i]=0;

    scanf("%s",c+1);

    len=strlen(c+1);

    int now=1,l=0;

    for(int i=1;i<=len;i++){

      int tmp=c[i]-'a';

      for(;now&&!t[now].ch[tmp];now=t[now].prt);

      if(!now)now=1,l=0;

      else l=min(l,t[now].maxl)+1,now=t[now].ch[tmp];

      pic[now]=max(pic[now],l);

    }

    for(int j=cur;j;j--){

      int k=topo[j];

      pic[t[k].prt]=min(t[t[k].prt].maxl,max(pic[t[k].prt],pic[k]));

      ans[k]=min(ans[k],pic[k]);

    }

  }

  int res=0;

  for(int i=1;i<=cur;i++)res=max(res,ans[i]);

  printf("%d",res);

  return 0;

}