+#include <stdbool.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "allocsa.h"
+
+/* Knuth-Morris-Pratt algorithm.
+ See http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm
+ Return a boolean indicating success. */
+static bool
+knuth_morris_pratt (const char *haystack, const char *needle,
+ const char **resultp)
+{
+ size_t m = strlen (needle);
+
+ /* Allocate the table. */
+ size_t *table = (size_t *) allocsa (m * sizeof (size_t));
+ if (table == NULL)
+ return false;
+ /* Fill the table.
+ For 0 < i < m:
+ 0 < table[i] <= i is defined such that
+ rhaystack[0..i-1] == needle[0..i-1] and rhaystack[i] != needle[i]
+ implies
+ forall 0 <= x < table[i]: rhaystack[x..x+m-1] != needle[0..m-1],
+ and table[i] is as large as possible with this property.
+ table[0] remains uninitialized. */
+ {
+ size_t i, j;
+
+ table[1] = 1;
+ j = 0;
+ for (i = 2; i < m; i++)
+ {
+ unsigned char b = (unsigned char) needle[i - 1];
+
+ for (;;)
+ {
+ if (b == (unsigned char) needle[j])
+ {
+ table[i] = i - ++j;
+ break;
+ }
+ if (j == 0)
+ {
+ table[i] = i;
+ break;
+ }
+ j = j - table[j];
+ }
+ }
+ }
+
+ /* Search, using the table to accelerate the processing. */
+ {
+ size_t j;
+ const char *rhaystack;
+ const char *phaystack;
+
+ *resultp = NULL;
+ j = 0;
+ rhaystack = haystack;
+ phaystack = haystack;
+ /* Invariant: phaystack = rhaystack + j. */
+ while (*phaystack != '\0')
+ if ((unsigned char) needle[j] == (unsigned char) *phaystack)
+ {
+ j++;
+ phaystack++;
+ if (j == m)
+ {
+ /* The entire needle has been found. */
+ *resultp = rhaystack;
+ break;
+ }
+ }
+ else if (j > 0)
+ {
+ /* Found a match of needle[0..j-1], mismatch at needle[j]. */
+ rhaystack += table[j];
+ j -= table[j];
+ }
+ else
+ {
+ /* Found a mismatch at needle[0] already. */
+ rhaystack++;
+ phaystack++;
+ }
+ }
+
+ freesa (table);
+ return true;
+}