0

See the function search below, it returns count but I don't see where this variable count acts/works (the function is found in a library , click here to download the source code, you will find kmp.c in \source\algos):

#include "include/define.h"
#include "include/main.h"

void preKmp(unsigned char *x, int m, int kmpNext[]) {
   int i, j;
   i = 0;
   j = kmpNext[0] = -1;
   while (i < m) {
      while (j > -1 && x[i] != x[j])
         j = kmpNext[j];
      i++;
      j++;
      if (i<m && x[i] == x[j])
         kmpNext[i] = kmpNext[j];
      else
         kmpNext[i] = j;
   }
}


int search(unsigned char *x, int m, unsigned char *y, int n) {
   int i, j, kmpNext[XSIZE], count;

   /* Preprocessing */
   BEGIN_PREPROCESSING
   preKmp(x, m, kmpNext);
   END_PREPROCESSING

   /* Searching */
   BEGIN_SEARCHING
   count = 0;
   i = j = 0;
   while (j < n) {
      while (i > -1 && x[i] != y[j])
         i = kmpNext[i];
      i++;
      j++;
      if (i >= m) {
         OUTPUT(j - i);
         i = kmpNext[i];
      }
   }
   END_SEARCHING
   return count;
}

Can any one explain how it works?

1
  • Where are these MACROs defined? What do they do? Aug 8, 2022 at 13:39

1 Answer 1

1

The OUTPUT macro that is defined in ./source/algos/include/define.h looks like this:

#define OUTPUT(j)   count++

And in search you have

      if (i >= m) {
         OUTPUT(j - i);     // <- here
         i = kmpNext[i];
      }

which explains how count is updated.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.