28. Implement strStr()

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

分析

这就是字符串匹配算法

算法一：

brute forcetime complexity: O(nm)

space complexity: O(1)

class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle =="")return 0;
        int index = -1;
        int i=0, j = 0;
        for(i = 0; i < haystack.size(); i++){
            for(j = 0; j < needle.size() && i+j < haystack.size(); j++){
                if(needle[j] != haystack[i+j]){
                    break;
                }
            }
            if(j == needle.size())return index = i;
        }
        return index;
    }
};

但是该算法在最后一个case 会超时。

算法二：

KMP算法。

该算法的关键点在于生成一个部分匹配表 Partial Match Table（又叫 Failure function）

这样在移位的时候，就不用每次都是移动一个位置，而可以跳着移动。

而关于匹配表的计算可以参看http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm

class Solution {
public:
    int strStr(string haystack, string needle) {
        int m = haystack.length(), n = needle.length();
        if (!n) return 0;
        vector<int> lps = kmpProcess(needle);
        for (int i = 0, j = 0; i < m; ) {
            if (haystack[i] == needle[j]) { 
                i++;
                j++;
            }
            if (j == n) return i - j;
            if (i < m && haystack[i] != needle[j]) {
                if (j) j = lps[j - 1];
                else i++;
            }
        }
        return -1;
    }
 
    vector<int> kmpProcess(string s) {
        vector<int> b(s.size(),0);
        int j = 0;
        //下面计算b[i]
        for (int i = 1; i < s.size(); i++) {
            while (j > 0 && s[i] != s[j]) 
                j = b[j - 1];//当前的widest border不满足要求，那么找到next widest border
            if (s[i] == s[j]) 
                j++;
            b[i] = j;
        }
        return b;
    }
};

null