knuth-morris-pratt algorithm

[sunilr245]

im trying to implement the kmp algorithm for fast string matching, im fairly new at programming so im having some trouble with syntax, i got the pseudocode from my text book

int prefix(const char *p)
{
    int m = strlen(p);
    int *a = new int[m];
    a[1] = 0;
    int k = 0;
    for(int q=2;q<m;q++)
    {
        while(k>0 && p[k+1]!=p[q]){
            k = a[k];
        }
        if(p[k+1]==p[q]){
            k=k+1;}
        a[q] = k;
    }
    return a;
}


int find_string(char *s, char *t)
{
    int a = prefix(t);
    int q = 0;
    for(int i=1;i<strlen(s);i++)
    {
        while(q>0 && t[q+1]!=s[i]){
            q = a[q];
        }
        if(t[q+1]==s[i]){q=q+1;}
        if(q==strlen(t)){
            return i-strlen(t);
            q = a[q];
        }
    }
    return -1;
}

//test code
int main(void)
{


   char sequence[100001];
   char pattern[1000];
   int i, j;
   for(i=0; i<100000; i++)
      sequence[i] = 'a';
   sequence[100000]='\0';
   for(i=0; i<4000; i++)
   {  j = rand()%100000;
      sequence[j]='b';
   }
   for(j=0; j< 1000; j++)
      pattern[j] = sequence[POSITION+j];
   pattern[1000] = '\0';
   if(find_string(sequence, pattern) == POSITION )
     printf("accepted\n");
   else
     printf("needs check?\n");
}

[weaknessforcats]

So what is your question exactly?

[sunilr245]

i get an errorr for my return value for the prefix function

[weaknessforcats]

The prefix function is to return an int but instead it is returning an int*.

And it leaks:

int *a = new int[m];

because this array is never deleted.

[sunilr245]

this is my code now, but the value i get still doesnt match the position, can anyone tell whats wrong with it?

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <cstring>
#define POSITION 89765


using namespace std;

void kmptable(const char *x, int T[])
{
    int n = strlen(x);
	int k=-1;
	int i=1;
	T[0]=-1;
	T[1]=0;
	for(i=1;i<n;i++)
	{
		while(k>-1&&x[k+1]!=x[i])
		{
		    k=T[k];
		}
		if(x[i]==x[k+1])
		{
            k++;
		}
		T[i]=k;
	}
}

int find_string(const char *s, const char *t)
{
    int m = strlen(s);
    int n = strlen(t);
	int i=0;
	int T[strlen(t)];
	kmptable(t, T);
	int k=-1;
	for(i=0;i<m;i++)
	{
		while(k>-1&&t[k+1]!=s[i])
		    k=T[k];
		if(s[i]==t[k+1])
		    k++;
		if(k==n-1)
			return i-n+1;
	}
	return -1;
}


int main(void)
{


   char sequence[100001];
   char pattern[1000];
   int i, j;
   for(i=0; i<100000; i++)
      sequence[i] = 'a';
   sequence[100000]='\0';
   for(i=0; i<4000; i++)
   {  j = rand()%100000;
      sequence[j]='b';
   }
   for(j=0; j< 1000; j++)
      pattern[j] = sequence[POSITION+j];
   pattern[1000] = '\0';
   if(find_string(sequence, pattern) == POSITION )
     printf("accepted\n");
   else
     printf("needs check?\n");
}