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


  • 1
    V

    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;    
    }

Log in to reply
 

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