OJ Board

thx:)

hamburger wrote:thx:)

http://acm.uva.es/p/v106/10679.html

hi ,i used KMP for this problem(10679).
it gets lime limit exceeded.

is my implementation wrong.please help

#include<stdio.h>
#include<malloc.h>
#include<string.h>

char p[100010],q[1100];
long f[1100];
long lenp,lenq;

void refresh()
{
int i;
q[0]=0;
for(i=0;i<1100;i++)
{
f=0;
}
}

void failure()
{
long i=1,j=0;
f[0]=0;

while(i<lenq)
{
if(q[j]==q)
{
f=j+1;
i++;
j++;
}
else if(j>0)
{
j=f[j-1];
}
else
{
f=0;
i++;
}
}
}

int KMP()
{
long i=0,j=0;

while(i<lenp)
{
if(q[j]==p)
{
if(j==lenq-1)
{
return 1;
}
i++;
j++;
}
else if(j>0)
{
j=f[j-1];
}
else i++;
}
return 0;
}

void main()
{
int N,l;
scanf("%d",&N);

while(N-->0)
{
scanf("%s %d",p,&l);
lenp=strlen(p);

while(l-->0)
{
scanf("%s",q);
lenq=strlen(q);
failure();
if(KMP())printf("y\n");
else printf("n\n");
refresh();
}
}
}

chops wrote:hi ,i used KMP for this problem(10679).
it gets lime limit exceeded.

I didn't check your code carefully , but you seem to rebuild your failure table for each query, and that is too time consuming. You should build it only once for the big string, then use the obtained table to process the queries.

thanks a lot.
that little thing didnt came to my mind.
i thought there was problem in my implementation.