# O(n+m) runtime, O(m) space; using KMP algorithm.

• Here goes the code that uses Knuth-Morris-Pratt algorithm in O(n+m) run time. It uses O(m) space as it builds a prefix table on pattern/needle.

``````void prefixTable(char *pattern, int *pi) {
int k = 0, q;
pi[0] = 0;
for (q = 1; q < strlen(pattern); q++) {
while (k > 0 && pattern[k] != pattern[q])
k = pi[k-1];
if (pattern[k] == pattern[q])
k = k + 1;
pi[q] = k;
}
}

int strStr(char* haystack, char* needle) {
int i;
int q = 0;     // number of characters matched
int n = strlen(haystack), m = strlen(needle);
int *pi;

if (m == 0) return 0;
if (m > n) return -1;

pi = (int *) malloc (sizeof(int) * m);
prefixTable(needle, pi);

for (i = 0; i < n; i++) {       //scan the text from left to right
while (q > 0 && needle[q] != haystack[i])
q = pi[q - 1];    //next character does not match
if (needle[q] == haystack[i])
q = q + 1;        // next character matches
if (q == m) {             // is all of P matched ?
free(pi);
return i - m + 1;
}
}
free(pi);
return -1;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.