Cod sursa(job #218623)

Utilizator c_iulyanCretu Iulian c_iulyan Data 2 noiembrie 2008 20:03:42
Problema Substr Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define N 19000
#define LG 20
#define X (const xx *)

struct xx
{
long x,y,p;
};

xx l[N];
long n,p[LG][N],lg,k;
char s[N];

int cmp(const void *a,const void *b)
{
return (X a)->x==(X b)->x?(X a)->y-(X b)->y:(X a)->x-(X b)->x;
}

void go()
{
long i,j,k;
for(i=0;i<n;i++)
	p[0][i]=s[i];
    
for(k=1,j=1;k<n*2;j++,k*=2)
	{
    for(i=0;i<n;i++)
    	{
        l[i].x=p[j-1][i];
        l[i].y=i+k>=n?-1:p[j-1][i+k];
        l[i].p=i;
        }

    qsort(l,n,sizeof(xx),cmp);

    for(i=0;i<n;i++)
    	p[j][l[i].p]=i&&l[i].x==l[i-1].x&&l[i].y==l[i-1].y?p[j][l[i-1].p]:i;
    }

lg=j-1;
}

long lcp(long x,long y)
{
long R=0,i;

if(x==y) return n-x;

for(i=lg;i>=0;i--)
	if(p[i][x]==p[i][y])
    	{
        x+=1<<i;
        y+=1<<i;
        R+=1<<i;
        }
return R;
}

int main()
{
freopen("substr.in","r",stdin);
freopen("substr.out","w",stdout);

scanf("%ld%ld%s",&n,&k,s);

go();

long R=0;
for(long i=0;i<n-k;i++)
   	{
    long q=lcp(l[i].p,l[i+k-1].p);
    R=R<q?q:R;
    }
    
printf("%ld",R);

return 0;
}