## Please tell me the number of KMP's application problems,thx.

Let's talk about algorithms!

Moderator: Board moderators

hamburger
New poster
Posts: 6
Joined: Wed Sep 24, 2003 7:46 am

### Please tell me the number of KMP's application problems,thx.

thx:)

lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:

### Re: Please tell me the number of KMP's application problems,

chops
New poster
Posts: 9
Joined: Sat Jan 29, 2005 10:48 pm
Location: dhaka
Contact:
hi ,i used KMP for this problem(10679).
it gets lime limit exceeded.

#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();
}
}
}

nnahas
New poster
Posts: 40
Joined: Mon Nov 01, 2004 7:56 pm
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.

chops
New poster
Posts: 9
Joined: Sat Jan 29, 2005 10:48 pm
Location: dhaka
Contact:
thanks a lot.
that little thing didnt came to my mind.
i thought there was problem in my implementation.