473,325 Members | 2,816 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,325 software developers and data experts.

knuth-morris-pratt algorithm

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
Expand|Select|Wrap|Line Numbers
  1. int prefix(const char *p)
  2. {
  3.     int m = strlen(p);
  4.     int *a = new int[m];
  5.     a[1] = 0;
  6.     int k = 0;
  7.     for(int q=2;q<m;q++)
  8.     {
  9.         while(k>0 && p[k+1]!=p[q]){
  10.             k = a[k];
  11.         }
  12.         if(p[k+1]==p[q]){
  13.             k=k+1;}
  14.         a[q] = k;
  15.     }
  16.     return a;
  17. }
  18.  
  19.  
  20. int find_string(char *s, char *t)
  21. {
  22.     int a = prefix(t);
  23.     int q = 0;
  24.     for(int i=1;i<strlen(s);i++)
  25.     {
  26.         while(q>0 && t[q+1]!=s[i]){
  27.             q = a[q];
  28.         }
  29.         if(t[q+1]==s[i]){q=q+1;}
  30.         if(q==strlen(t)){
  31.             return i-strlen(t);
  32.             q = a[q];
  33.         }
  34.     }
  35.     return -1;
  36. }
  37.  
  38. //test code
  39. int main(void)
  40. {
  41.  
  42.  
  43.    char sequence[100001];
  44.    char pattern[1000];
  45.    int i, j;
  46.    for(i=0; i<100000; i++)
  47.       sequence[i] = 'a';
  48.    sequence[100000]='\0';
  49.    for(i=0; i<4000; i++)
  50.    {  j = rand()%100000;
  51.       sequence[j]='b';
  52.    }
  53.    for(j=0; j< 1000; j++)
  54.       pattern[j] = sequence[POSITION+j];
  55.    pattern[1000] = '\0';
  56.    if(find_string(sequence, pattern) == POSITION )
  57.      printf("accepted\n");
  58.    else
  59.      printf("needs check?\n");
  60. }
  61.  
  62.  
  63.  
Dec 14 '13 #1
4 2014
weaknessforcats
9,208 Expert Mod 8TB
So what is your question exactly?
Dec 14 '13 #2
i get an errorr for my return value for the prefix function
Dec 15 '13 #3
weaknessforcats
9,208 Expert Mod 8TB
The prefix function is to return an int but instead it is returning an int*.

And it leaks:
Expand|Select|Wrap|Line Numbers
  1. int *a = new int[m];
  2.  
because this array is never deleted.
Dec 15 '13 #4
this is my code now, but the value i get still doesnt match the position, can anyone tell whats wrong with it?

Expand|Select|Wrap|Line Numbers
  1. #include <iostream>
  2. #include <stdlib.h>
  3. #include <stdio.h>
  4. #include <cstring>
  5. #define POSITION 89765
  6.  
  7.  
  8. using namespace std;
  9.  
  10. void kmptable(const char *x, int T[])
  11. {
  12.     int n = strlen(x);
  13.     int k=-1;
  14.     int i=1;
  15.     T[0]=-1;
  16.     T[1]=0;
  17.     for(i=1;i<n;i++)
  18.     {
  19.         while(k>-1&&x[k+1]!=x[i])
  20.         {
  21.             k=T[k];
  22.         }
  23.         if(x[i]==x[k+1])
  24.         {
  25.             k++;
  26.         }
  27.         T[i]=k;
  28.     }
  29. }
  30.  
  31. int find_string(const char *s, const char *t)
  32. {
  33.     int m = strlen(s);
  34.     int n = strlen(t);
  35.     int i=0;
  36.     int T[strlen(t)];
  37.     kmptable(t, T);
  38.     int k=-1;
  39.     for(i=0;i<m;i++)
  40.     {
  41.         while(k>-1&&t[k+1]!=s[i])
  42.             k=T[k];
  43.         if(s[i]==t[k+1])
  44.             k++;
  45.         if(k==n-1)
  46.             return i-n+1;
  47.     }
  48.     return -1;
  49. }
  50.  
  51.  
  52. int main(void)
  53. {
  54.  
  55.  
  56.    char sequence[100001];
  57.    char pattern[1000];
  58.    int i, j;
  59.    for(i=0; i<100000; i++)
  60.       sequence[i] = 'a';
  61.    sequence[100000]='\0';
  62.    for(i=0; i<4000; i++)
  63.    {  j = rand()%100000;
  64.       sequence[j]='b';
  65.    }
  66.    for(j=0; j< 1000; j++)
  67.       pattern[j] = sequence[POSITION+j];
  68.    pattern[1000] = '\0';
  69.    if(find_string(sequence, pattern) == POSITION )
  70.      printf("accepted\n");
  71.    else
  72.      printf("needs check?\n");
  73. }
  74.  
  75.  
  76.  
Dec 16 '13 #5

Sign in to post your reply or Sign up for a free account.

Similar topics

6
by: Jack Smith | last post by:
Hello, any help appreciated with following problem. I figured out the algorithm (I think), just having trouble proving it is optimal. Suppose we are given n tasks each of which takes 1 unit...
10
by: bpontius | last post by:
The GES Algorithm A Surprisingly Simple Algorithm for Parallel Pattern Matching "Partially because the best algorithms presented in the literature are difficult to understand and to implement,...
32
by: Cmorriskuerten | last post by:
HI, is this is this solution to test if a number is a prime number or not: /* * Is n a prime number? * Return TRUE (1): n is a prime number * Return FALSE (0): n is a *not* a prime number...
113
by: Bonj | last post by:
I was in need of an encryption algorithm to the following requirements: 1) Must be capable of encrypting strings to a byte array, and decyrpting back again to the same string 2) Must have the same...
4
by: FBM | last post by:
Hi, I am working on a program that simulates one of the elements of ATM. The simulation stores events which occurs every some milliseconds for a certain amount of time. Every time that an event...
2
by: Julio C. Hernandez Castro | last post by:
Dear all, We have just developped a new block cipher called Raiden, following a Feistel Network structure by means of genetic programming. Our intention now consists on getting as much feedback...
0
by: aruna | last post by:
hey guys i earlier had very valuable responses from you all for base64 encoding algorithm.so thank for that. so now i need your assistance to do a float encoding algorithm. you may wonder why i'm...
1
by: almurph | last post by:
Hi everyone, Concerning the Needleman-Wunsch algorithm (cf. http://en.wikipedia.org/wiki/Needleman-Wunsch_algorithm) I have noticed a possible loop. Inside the algorithm there is an...
9
Rabbit
by: Rabbit | last post by:
Introduction The Advanced Encryption Standard is the algorithm that won the National Insitute of Standards and Technology's (NIST) search for a standardized encryption algorithm in 2001. In 2002, it...
24
Rabbit
by: Rabbit | last post by:
INTRODUCTION The Secure Hash Algorithm 2 is a series of cryptographic hash algorithms designed by the US National Security Agency (NSA) and published by the National Institute of Standards and...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.