title: Knuth-Morris-Pratt implementation in pure C
body: <p>I have the next KMP-implementation:</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;string.h&gt;
  
  int kmp(char substr[], char str[])
  {
     int i, j, N, M;
  
     N = strlen(str);
     M = strlen(substr);
  
     int *d = (int*)malloc(M * sizeof(int));
     d[0] = 0;
  
     for(i = 0, j = 0; i &lt; M; i++)
     {
        while(j &gt; 0 &amp;&amp; substr[j] != substr[i])
        {
           j = d[j - 1];
        }
  
        if(substr[j] == substr[i])
        {
           j++;
           d[i] = j;
        }
     }
  
     for(i = 0, j = 0; i &lt; N; i++)
     {
        while(j &gt; 0 &amp;&amp; substr[j] != str[i])
        {
           j = d[j - 1];
        }
  
        if(substr[j] == str[i])
        {
           j++;
        }
  
        if(j == M)
        {
           free(d);
           return i - j + 1;
        }
     }
  
     free(d);
  
     return -1;
  }
  
  int main(void)
  {
     char substr[] = "World",
        str[] = "Hello World!";
  
     int pos = kmp(substr, str);
  
     printf("position starts at: %i\r\n", pos);
  
     return 0;
  }
  </code></pre>
  
  <p>You can test it here: <a href="http://liveworkspace.org/code/d2e7b3be72083c72ed768720f4716f80" rel="nofollow">http://liveworkspace.org/code/d2e7b3be72083c72ed768720f4716f80</a></p>
  
  <p>It works well on small strings, and I have tested it with a large loop, on this way all is fine.</p>
  
  <p>But if I change the substring I'm searching for and the complete string to these:</p>
  
  <pre><code>char substr[] = "%end%",
  str[] = "&lt;h1&gt;The result is: &lt;%lua% oleg = { x = 0xa }
           table.insert(oleg, y) oleg.y = 5 print(oleg.y) %end%&gt;&lt;/h1&gt;";
  </code></pre>
  
  <p>Only after first try, this implementation fails...</p>
  
  <p>Please, could you help me with repairing implementation of KMP to make the algorithm work with such data in strings...</p>