title: Pattern matching in long text string
body: <p>I wrote this code and it works in some cases. Sometimes, however, it fails, and I just can't see why. Can someone please help me spot the error?</p>
  
  <p>It works for:
  String: <code>ishanthakkar ishan</code>
  patter: <code>ishan</code></p>
  
  <p>But it fails for:</p>
  
  <p>String: <code>cpr ograming</code>
  patter: <code>cpr</code></p>
  
  <p>Source:</p>
  
  <pre><code>#include &lt;stdio.h&gt;    
  #include &lt;stdlib.h&gt;    
  #include &lt;string.h&gt;
  
  int *compute_prefix_function(char *pattern, int psize)
  {
      int k = -1;
      int i = 1;
      int *pi = malloc(sizeof(int)*psize);
      if (!pi)
          return NULL;
  
      pi[0] = k;
      for (i = 1; i &lt; psize; i++) {
          while (k &gt; -1 &amp;&amp; pattern[k+1] != pattern[i])
              k = pi[k];
          if (pattern[i] == pattern[k+1])
              k++;
          pi[i] = k;
      }
      return pi;
  }
  </code></pre>
  
  <p>// This function find matching string in O(n) time, so iterate through text string only once, when unmatching character found; it proceed with next character and start comparing with first character of string to be searched i.e pattern</p>
  
  <pre><code>int kmp(char *target, int tsize, char *pattern, int psize)
  {
      int i;
      int *pi = compute_prefix_function(pattern, psize);
      int k = -1;
      if (!pi)
          return -1;
  
      for (i = 0; i &lt; tsize; i++) {
          while (k &gt; -1 &amp;&amp; pattern[k+1] != target[i])
              k = pi[k];
          if (target[i] == pattern[k+1])
              k++;
  
          if (k == psize - 1) {
              free(pi);
              return i-k;
          }
      }
  
      free(pi);
      return -1;
  }
  
  int main(int argc, const char *argv[])
  {
      char target[200];
      char *ch = target;
      char pattern[20];
      int i;
  
      printf("Enter the string: \n");
      fgets(target,100,stdin);
  
      printf("Enter the string to be matched: \n");
      fgets(pattern,20,stdin);
  
      i = kmp(target, strlen(target), pattern, strlen(pattern)); 
      if (i &gt;= 0)
          printf("matched @: %s\n", ch + i);
  
      getch();
      return 0;
  }
  </code></pre>