[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：two pointers

这是brutal force解法，对haystack中每个字符，检查是否能以该字符为首字母的substring能和needle吻合。

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

思路2：KMP

高大上的解法，最优的O(n)复杂度。但无论理解还是写都很不容易。看过不少书上的解释，觉得讲得最清楚的还是网上的一篇帖子：

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<int> KMPpreprocessing(char *s) { int n = strlen(s); vector<int> match(n,-1); int j = -1; for(int i=1; i<n; i++) { while(j>=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<int> match = KMPpreprocessing(needle); int j = -1; for(int i=0; i<m; i++) { while(j>=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; } };