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

1 comment: