实现strStr（）—— KMP ——记录（C++）

2022-05-05 23:39:55

这一题可以说是做题以来收获最大的一道题了，虽然它是放在简单题范畴里的，但是它同样可以用较厉害的算法解答。当然，我只会暴力解答。

暴力的代码就不放了。

这道题我目前能够写出三种答案：

①暴力解答；

②直接调用内置函数；

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

③利用KMP算法

（之前从没了解过，这也是我今天做题最大的收获）

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        if (m == 0) {
            return 0;
        }
        vector<int> pi(m);
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && needle[i] != needle[j]) {
                j = pi[j - 1];
            }
            if (needle[i] == needle[j]) {
                j++;
            }
            pi[i] = j;
        }
        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && haystack[i] != needle[j]) {
                j = pi[j - 1];
            }
            if (haystack[i] == needle[j]) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }
};

按照我的理解大概解释一下KMP算法，当然，我主要是记录，并不能讲的多清楚。


    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        if (m == 0) {
            return 0;
        }
        vector<int> pi(m);
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && needle[i] != needle[j]) {
                j = pi[j - 1];
            }
            if (needle[i] == needle[j]) {
                j++;
            }
            pi[i] = j;
        }

代码的上半部分，用一个数组来记录needle字符串的各个长度的相同的最长前缀和最长后缀的长度——n；

例：输入needle=aacbacaa;

那么"a"——n=0;

"aa"——n=1；

“aac”——n=0;

……

“aacbacaa"——n=2;

分别将以上结果输入pi数组中；

则得到needle各个长度所对应的最长前缀和最长后缀的长度——n；


        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && haystack[i] != needle[j]) {
                j = pi[j - 1];
            }
            if (haystack[i] == needle[j]) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }

下半部分代码与上半部分代码相似，但是却有些不同；

我以画图的形式大概讲述：