28. Leetcode笔记——子字符串搜索（KMP）

Problem

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
解决一个大字符串中的字串搜索问题，返回第一个出现的子串的位置；
值得注意的是： 如果子串为空，则会返回0（这与C++中的strstr()函数一致，）

Brute-Force Solution

class Solution {
public:
    int strStr(string haystack, string needle) {
       
        int m = haystack.length(), n = needle.length();
        if (!n) {
            return 0;
        }
        for (int i = 0; i < m - n + 1; i++) {
            int j = 0;
            //fix i in the original string
            for (; j < n; j++) {
                if (haystack[i + j] != needle[j]) {
                    break;
                }
            }
            if (j == n) {
                return i;
            }
        }
        return -1;
    }
};

KMP 算法

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;
    }
private:
    vector<int> kmpProcess(string& needle) {
        int n = needle.length();
        vector<int> lps(n, 0);
        // len denotes the matching substring length, comparing to the beginning
        for (int i = 1, len = 0; i < n; ) {
            if (needle[i] == needle[len]) {
                lps[i++] = ++len;
            } else if (len) {
                len = lps[len - 1];
            } else {
                lps[i++] = 0;
            }
        }
        return lps;
    }
};

Discussion

今天的问题其实很简单，官方推荐的就是暴力搜索的方式，即比较挨个子串首字母和母串的首字母，如果相等就继续检查下去，如果不等，母串的位置加一，同样的操作。

但是这个问题也可以通过KMP算法来进行简化。这个算法因为三个人同时提出而得名（Knuth-Morris-Pratt字符串查找算法）。在我看来，这种算法的本质是属于一种效果明显的pruning的方式。

具体的介绍可以参见 维基百科 (中文页方便理解算法，我下午还要赶着看paper..)

主要的思想是这样的：
在子串中设置一个相对向量，来标记每个位置与该子串首字母的联系，比如说下图：

kmp
i为4-5的时候，该位置对应的字母是与开头字母相匹配的，即如果在 的位置失配，我们便不需要从头开始比较，只需要将子串在母串中的开头位置移动到相对应的 的位置，并且从 的位置开始比较就可以了～详细的算法请参考维基百科。理解了之后实现也是比较麻烦的，我这里便不再详细探讨。抛出leetcode上的一个好答案，还有CSDN上的一篇博客。