## Monday, November 17, 2014

### [LeetCode] Implement strStr() - KMP解法

Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18``` ```class Solution { public: int strStr(char *haystack, char *needle) { if(!*needle) return 0; if(!*haystack) return -1; int m = strlen(haystack), n = strlen(needle); for(int i=0; i<=m-n; i++) { for(int j=0; j<=n; j++) { char *p1 = haystack+i+j; char *p2 = needle+j; if(!*p2) return i; if(*p1 != *p2) break; } } return -1; } }; ```

http://www.matrix67.com/blog/archives/115

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30``` ```class Solution { public: vector KMPpreprocessing(char *s) { int n = strlen(s); vector match(n,-1); int j = -1; for(int i=1; i=0 && s[i]!=s[j+1]) j = match[j]; if(s[i]==s[j+1]) j++; match[i] = j; } return match; } int strStr(char *haystack, char *needle) { if(!*needle) return 0; if(!*haystack) return -1; int m = strlen(haystack), n = strlen(needle); vector match = KMPpreprocessing(needle); int j = -1; for(int i=0; i=0 && haystack[i]!=needle[j+1]) j = match[j]; if(haystack[i]==needle[j+1]) j++; if(j==n-1) return (i-n+1); } return -1; } }; ```