Home > OS >  How the counting is conducted in this function?
How the counting is conducted in this function?

Time:08-09

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?

CodePudding user response:

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.

  • Related