目录

题目：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.

题意：

该题目就是实现strstr()函数，该函数C语言原型如下：返回字符串str1在str2中的位置。

extern char *strstr(char *str1, const char *str2);

解法：

暴力求解法

最直接的实现方式就是暴力求解法，如下代码所示，

class Solution {
    public:
        int strStr(string haystack, string needle) {
            return bruth(haystack, needle);
        }

    private:
        int bruth(string text, string pattern) {
            int M = pattern.length();
            int N = text.length();
            if (M == 0) return 0;
            if (N == 0) return -1;
            for (int i = 0; i <= N - M; ++i) {
                int j = 0;
                for (; j < M; ++j) {
                    if (text.at(i + j) != pattern.at(j))
                        break;
                }
                if (j == M) return i;
            }
            return -1;
        }
}

在最坏的情况下，暴力子字符串查找算法在长度为N的文本中查找长度为M的模式字符串需要O(NM)次字符串比较。

我们可以将上面的实现方法进行一定的修改，让大家能看到i指针的回退，如下代码所示，当i指针指向字符和j指向字符发生失配，i便会回退j个位置（此时j是失配前模式串的匹配项个数），同时j指向模式串的第一个位置。该段代码和上面代码其实是等效的。

class Solution {
public:
    int strStr(string haystack, string needle) {
        return bruth(haystack, needle);
    }

private:
    int bruth(string text, string pattern) {
        int M = pattern.length();
        int N = text.length();
        if (M == 0) return 0;
        if (N == 0) return -1;
        int i = 0;
        int j = 0;
        for (; i < N && j < M; ++i) {
            if (text.at(i) == pattern.at(j)) j++;
            else {  i -= j; j = 0; }
        }
        if (j == M) return i - M;
        else return -1;
    }
}

那我们就可以很明显的看到，当模式串中j指向位置字符不匹配的时候，其实前面通过匹配我们已经获知了一部分文本的情况，因此如果能够利用这一部分已知的情况来加大模式串移动的有效性。KMP算法就是利用字符串匹配失效之前部分匹配的这个有用信息，通过保持文本指针不回退，仅有效移动模式字符串的位置来进行有效查找的。

KMP算法

KMP算法常用于在一个文本串S内查找一个模式串P 的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人同时独立发现，后取这3人的姓氏命名此算法. 大家可以参看july的Blog，讲解的是我目前看到最详细的了。

KMP算法实现：

 class Solution {
    public:
        int strStr(string haystack, string needle) {
            return kmp(haystack, needle);
        }
    private:
        // KMP
        int kmp(string text, string pattern) {
            int M = pattern.length();
            int N = text.length();
            if (M == 0) return 0;
            if (N == 0) return -1;
            int i = 0;
            int j = 0;
    
            int* next = new int[M];
            calculateNext(pattern, next);
            for (; i < N && j < M; ++i) {
                if ( j == -1 || text.at(i) == pattern.at(j) ) j++;
                else { i--; j = next[j]; }  // i维持不变，j跳转位置由next数组决定
            }
            delete[] next;
    
            if (j == M) return i - M;
            else return -1;
        }
        void calculateNext(string pattern, int* next) {
            if (pattern.length() == 0 || next == nullptr) return;
            next[0] = -1;
            int i = 0;
            int k = -1;
            while (i < pattern.length() - 1) {
                if (k == -1 || pattern.at(k) == pattern.at(i)) {
                    ++i;
                    ++k;
                    next[i] = k;
                }
                else {
                    k = next[k];
                }
            }
        }
    }