SDOI2008[Sandy的卡片]

赤裸裸的后缀数组。


CODE:


/*


AUTHOR: Su Jiao


DATE: 2010-7-27


DESCRIPTION:


山东2008年省选 Sandy的卡片


*/


#include <stdio.h>


 


#define max(a,b) ((a)>(b)?(a):(b))


const int MAXALPHABET=1000000;


const int MAXLENGTH=1000000;


typedef int string[MAXLENGTH];


typedef int* int_pointer;


int sort[max(MAXALPHABET,MAXLENGTH)];


int _SA[MAXLENGTH],_rank[MAXLENGTH],_TSA[MAXLENGTH],_Trank[MAXLENGTH];


int_pointer SA=_SA,rank=_rank,TSA=_TSA,Trank=_Trank;


void get_SA(string s,int length)


{


     for (int i=0;i<MAXALPHABET;i++) sort[i]=0;


     for (int i=1;i<=length;i++) sort[s[i]]++;


     for (int i=1;i<MAXALPHABET;i++) sort[i]+=sort[i-1];


     for (int i=1;i<=length;i++) SA[sort[s[i]]–]=i;


     rank[SA[1]]=1;


     for (int i=2;i<=length;i++)


         if (s[SA[i]]==s[SA[i-1]]) rank[SA[i]]=rank[SA[i-1]];


         else rank[SA[i]]=rank[SA[i-1]]+1;


     for (int block=1;block<length;block<<=1)


     {


         for (int i=1;i<=length;i++) sort[rank[SA[i]]]=i;


         for (int i=length;i>=1;i–)


             if (SA[i]-block>=1)


                TSA[sort[rank[SA[i]-block]]–]=SA[i]-block;


         for (int i=length-block+1;i<=length;i++)


             TSA[sort[rank[i]]–]=i;


         int_pointer swap;


         swap=SA,SA=TSA,TSA=swap;


         swap=rank,rank=Trank,Trank=swap;


         rank[SA[1]]=1;


         for (int i=2;i<=length;i++)


             if (Trank[SA[i]]==Trank[SA[i-1]]


                 &&Trank[SA[i]+block]==Trank[SA[i-1]+block])


                rank[SA[i]]=rank[SA[i-1]];


             else rank[SA[i]]=rank[SA[i-1]]+1;


     }


}


int height[MAXLENGTH];


void get_height(string s,int length)


{


     for (int i=1,h=0;i<=length;i++)


     {


         if (h) h–;


         if (rank[i]!=1)


         {


            int j=SA[rank[i]-1];


            while (s[i+h]==s[j+h]) h++;


         }


         height[rank[i]]=h;


     }


}


 


int N;


string s;


int length;


int id[MAXLENGTH];


int found_time;


int found[MAXLENGTH];


bool check(int value)


{


     int i=1;


     while (i<=length)


     {


           while (i<=length&&height[i]<value) i++;


           int found_counter=1;


           found[id[SA[i-1]]]=++found_time;


           while (i<=length&&height[i]>=value)


           {


                 if (found[id[SA[i]]]!=found_time)


                 {


                    found[id[SA[i]]]=found_time;


                    found_counter++;


                 }


                 i++;


           }


           if (found_counter==N) return true;


     }


     return false;


}


int main()


{


    scanf(“%d”,&N);


    for (int i=1;i<=N;i++)


    {


        int M,a,b;


        scanf(“%d%d”,&M,&b);


        for (int j=1;j<M;j++)


        {


            a=b;


            scanf(“%d”,&b);


            s[++length]=b-a+100000;


            id[length]=i;


        }


        s[++length]=i;


        id[length]=i;


    }


    get_SA(s,length);


    get_height(s,length);


    if (N==1) printf(“%d\n”,length-1);


    else


    {


        int L=0,R=length;


        while (L+1!=R)


        {


              int mid=(L+R)>>1;


              if (check(mid)) L=mid;


              else R=mid;


        }


        printf(“%d\n”,L+1);


    }


}


 


留下评论

您的电子邮箱地址不会被公开。 必填项已用*标注