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

本文主要是介绍实现strStr（）—— KMP ——记录（C++），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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

暴力的代码就不放了。

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

①暴力解答；

②直接调用内置函数；

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

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

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

 输入haystack为”abacababca“

输入needle为“abab”

开始作比较，当作比较到第四位时，"b"!="c"；

得到"aba"的n值，即n=1；

则以以下形式开始下一轮比较，以此类推，直至结束；

再次比较出不等：

 找到对象，返回对应值。

虽然讲的不是很清楚，但是我觉得图片能说明的事情已经挺多的了！

加油~！

这篇关于实现strStr（）—— KMP ——记录（C++）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！