bzoj4698

题解：

后缀数组

对所有序列差分一下

公共串的长度+1就是答案了

二分 扫一遍height即可,..

代码：

#include <bits/stdc++.h>

using namespace std;

const int N=,M=;

int n,mn=2e9,mx=,lt,rt=2e9,mid,ans=,a[N][N],l[N],b[M],id[M];

int tot,vis[N],cnt,sa[M],ta[M],rk[M],ht[M],wa[M],wb[M],ca[M],cb[M];

int check(int k)

{

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

        {

        if (ht[i]<k)

         {

             memset(vis,,sizeof(vis));

            cnt=;

         }

        if (!vis[id[sa[i]]])vis[id[sa[i]]]=,++cnt;

        if (cnt==n)return ;

       }

      return ;

}

int main()

{

      scanf("%d",&n);

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

     {

        scanf("%d",l[i]);

        for (int j=;j<=l[i];j++)

         {

              scanf("%d",&a[i][j]);

              if (j>)mx=max(mx,a[i][j]-a[i][j-]);

         }

        rt=min(rt,l[i]);

       }

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

        {

        for (int j=;j<=l[i];j++)

         {

             b[++tot]=a[i][j]-a[i][j-];

            id[tot]=i;

         }

        b[++tot]=++mx;

       }

      for (int i=;i<=tot;i++)mn=min(mn,b[i]);

      for (int i=;i<=tot;i++)b[i]=b[i]-mn+,mx=max(mx,b[i]);

      memset(ca,,sizeof(ca));

      for (int i=;i<=tot;i++)ca[b[i]]++;

      for (int i=;i<=mx;i++)ca[i]+=ca[i-];

      for (int i=tot;i>=;i--)sa[ca[b[i]]--]=i;

      rk[sa[]]=;

      for (int i=;i<=tot;i++)rk[sa[i]]=rk[sa[i-]]+(b[sa[i]]!=b[sa[i-]]);

      for (int k=;rk[sa[tot]]<tot;k<<=)

       {

        memset(ca,,sizeof(ca));

        memset(cb,,sizeof(cb));

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

         {

             ca[wa[i]=rk[i]]++;

            cb[wb[i]=i+k<=tot?rk[i+k]:]++;

         }

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

         {

             ca[i]+=ca[i-];

            cb[i]+=cb[i-];

         }

        for (int i=tot;i;i--)ta[cb[wb[i]]--]=i;

        for (int i=tot;i;i--)sa[ca[wa[ta[i]]]--]=ta[i];

        rk[sa[]]=;

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

         rk[sa[i]]=rk[sa[i-]]+(wa[sa[i]]!=wa[sa[i-]]||wb[sa[i]]!=wb[sa[i-]]);

       }

      for (int i=,j=;i<=tot;i++)

       {

        if (j)j--;

        while (b[i+j]==b[sa[rk[i]-]+j])j++;

        ht[rk[i]]=j;

       }

      while (lt<=rt)

       {

        if (check(mid=(lt+rt)>>))ans=mid+,lt=mid+;

        else rt=mid-;

       }

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

}