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

Let's talk about algorithms!

Moderator: Board moderators

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

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

Post by hamburger » Tue Nov 02, 2004 10:40 am

thx:)


chops
New poster
Posts: 9
Joined: Sat Jan 29, 2005 10:48 pm
Location: dhaka
Contact:

Post by chops » Sat Jan 29, 2005 11:03 pm

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

nnahas
New poster
Posts: 40
Joined: Mon Nov 01, 2004 7:56 pm

Post by nnahas » Sun Jan 30, 2005 1:35 am

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:

Post by chops » Sun Jan 30, 2005 9:33 pm

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

Post Reply

Return to “Algorithms”