SPOJ687[Repeats]

最长公共前缀,用后缀数组做的。


CODE:


/*


AUTHOR: Su Jiao


DATE: 2010-7-23


DESCRIPTION:


$DESCRIPTION


*/


#include <stdio.h>


#include <string.h>


 


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


const int LOG2_MAXLENGTH=16;


const int MAXLENGTH=1<<LOG2_MAXLENGTH;


const int MAXALPHABET=128;


typedef char string[MAXLENGTH];


int sort[max(MAXALPHABET,MAXLENGTH)];


int SA[MAXLENGTH],rank[MAXLENGTH],TSA[MAXLENGTH],Trank[MAXLENGTH];


void get_SA(string s,int length)


{


     memset(sort,0,sizeof(sort));


     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-1]]==s[SA[i]]) 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;


         Trank[TSA[1]]=1;


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


             if (rank[TSA[i-1]]==rank[TSA[i]]


                 &&rank[TSA[i-1]+block]==rank[TSA[i]+block])


                Trank[TSA[i]]=Trank[TSA[i-1]];


             else Trank[TSA[i]]=Trank[TSA[i-1]]+1;


         memcpy(SA,TSA,sizeof(SA));


         memcpy(rank,Trank,sizeof(rank));


     }


}


int height[MAXLENGTH];


void get_height(string s,int length)


{


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


     {


         if (h) h–;


         if (rank[i]-1>=1)


         {


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


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


         }


         height[rank[i]]=h;


     }


}


int log2[MAXLENGTH];


int rmq[LOG2_MAXLENGTH][MAXLENGTH];


void get_RMQ(int length)


{


     log2[1]=0;


     for (int i=2;i<=length;i++) log2[i]=log2[i-1]+(i==(i&(-i)));


     for (int i=1;i<=length;i++) rmq[0][i]=i;


     for (int log=1;log<=log2[length];log++)


     {


         int exp=1<<log,exp_div_2=exp>>1;


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


         {


             int a=rmq[log-1][i];


             int b=rmq[log-1][i+exp_div_2];


             rmq[log][i]=height[a]<height[b]?a:b;


         }


     }    


}


int RMQ(int a,int b)


{


    int log=log2[b-a+1];


    int exp=1<<log;


    a=rmq[log][a],b=rmq[log][b-exp+1];


    return height[a]<height[b]?a:b;


}


int LCP(int a,int b)


{


    a=rank[a],b=rank[b];


    if (a>b) return height[RMQ(b+1,a)];


    else return height[RMQ(a+1,b)];


}


 


int H;


int n;


string s;


int main()


{


    scanf(“%d\n”,&H);


    for (int h=0;h<H;h++)


    {


        scanf(“%d\n”,&n);


        for (int i=1;i<=n;i++) scanf(“%c\n”,s+i);


        s[n+1]=0;


        get_SA(s,n);


        get_height(s,n);


        get_RMQ(n);


        int answer=1;


        for (int repeat=1;repeat<n;repeat++)


            for (int start=1;start+repeat<=n;start+=repeat)


            {


                int lcp=LCP(start,start+repeat);


                int get=lcp/repeat+1;


                int maybe_start=start-(repeat-(lcp%repeat));


                if (maybe_start>=1)


                   if (LCP(maybe_start,maybe_start+repeat)>=repeat) get++;


                if (get>answer) answer=get;


            }


        printf(“%d\n”,answer);


    }


}