这个算法是我在leetcode刷题时，最开始适用了朴素匹配的思想去做，发现时间复杂度为O(n*m)（n为主串长度，m为子串长度），每次匹配失败都要回退到起点的下一个位置重新遍历。

朴素匹配算法

在朴素匹配中，当主串haystack与子串needle匹配失败时，主串指针会回退到初始位置 + 1，子串指针回退到 0，导致大量重复比较。

主串：ABC ABCDAB ABCDABCDABDE
子串：ABCDABD

当匹配到第 7 个字符（主串空格 vs 子串D）失败时，朴素算法会从主串第 2 个字符重新开始，而 KMP 算法能利用已匹配的ABCDAB信息，直接跳到更优的位置继续匹配。

例如我的写法如下：

int left = 0, right = 0;
int start = 0;
while (right < size) {
    while (left < haystack.size() && haystack[left] != needle[right]) {
        left++;
        start++;
        right = 0;
    }
    left++;
    right++;
}

KMP算法

前缀表（Next数组）

前缀表又称为部分匹配表，是KMP的核心，主要用于记录子串中每个位置的最长前缀后缀匹配长度，以此确定匹配失败时字串指针应回溯的位置。

前缀与后缀

前缀：

子串中除了最后一个字符外，所有以第一个字符开头的连续子串。

例如：ABCDAB的前缀为A、AB、ABC、ABCD、ABCDA。

后缀：

子串中除第一个字符外，所有以最后一个字符结尾的连续子串。
例：ABCDAB的后缀为B、AB、DAB、CDAB、BCDAB。

最长前缀后缀匹配长度：

前缀和后缀中最长的相同字串长度，

例如上方的ABCDAB的最长匹配为AB，长度为2.

 

前缀表

Next 数组的长度与子串相同，next[i]表示子串needle[0..i]的最长前缀后缀匹配长度。

步骤：

1. 初始化next[0] = 0(单个字符无前缀后缀)

2. 用双指针i（字串当前位置，从1开始）和j（当前最长匹配长度，初始化为0）遍历字串：

   • 若needle[i] == needle[j]：匹配成功，j++，next[i] = j，i++

   • 若needle[i] != needle[j]：

     • 若j > 0：回溯j = next[j-1]（利用之前的匹配信息）。
     • 若j == 0：无法匹配，next[i] = 0，i++。

所以其构建前缀表的过程如下：

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

则字符串ABCDABD的 Next 数组

索引i: 	0 1 2 3 4 5 6
字符:  	A B C D A B D
next[i]: 0 0 0 0 1 2 0

 

KMP匹配过程

利用前缀表，当主串与子串匹配失败时，不需要回退主串指针，只需根据前缀表调整子串指针：

1. 初始化主串指针i = 0,字串指针j = 0;

2. 遍历主串：

   • 若haystack[i] == needle[j]：两指针同时后移（i++，j++）

   • 若haystack[i] != needle[j]：

     • 若j > 0：子串指针回溯到next[j-1]（利用前缀表跳过无效比较）。
     • 若j == 0：主串指针后移（i++）

3. 当j == 子串长度：匹配成功，返回i - j（子串在主串中的起始位置）。
4. 遍历结束仍未匹配，返回-1。

匹配过程的代码如下：

for (int i = 0, j = 0; i < n; i++) {
    // 当不匹配时的回溯过程
    while (j > 0 && haystack[i] != needle[j]) {
        j = next[j - 1];
    }
    // 两者匹配时的操作，两个指针向后+1
    if (haystack[i] == needle[j]) {
        j++;
    }
    // 如果此时字串指针等于其长度了，说明其匹配成功了
    if (j == m) {
        return i - m + 1;
    }
}

// 全都没有匹配成功，返回-1
return -1;

 

完整代码

所以，leetcode28 的正确完整代码如下：

#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    int strStr(string haystack, string needle) {
        int hsize = haystack.size(), nsize = needle.size();
        if (nsize == 0) {
            return 0;   // 字串为空
        }

        if (hsize < nsize) {
            return -1;  // 主串比子串还短
        }

        // 构建前缀表
        vector<int> next(nsize, 0);
        for (int i = 1, j = 0; i < nsize; i++) {
            // 利用i创建j的前缀
            while (j > 0 && needle[i] != needle[j]) {
                j = next[j - 1];
            }

            if (needle[i] == needle[j]) {
                j++;  // 两者相等的时候，同时往后移动
            }
            next[i] = j;
        }

        // KMP匹配过程
        for (int i = 0, j = 0; i < hsize; i++) {
            while (j > 0 && haystack[i] != needle[j]) {
                j = next[j - 1];
            }

            // 两者匹配时，两个指针向后+1
            if (haystack[i] == needle[j]) {
                j++;
            }

            // 如果字串指针已经到了最后
            if (j == nsize) {
                return i - nsize + 1;
            }
        }
        return -1;
    }
};

int main()
{
    string hay = "mississippi";
    string need = "issip";
    Solution sol;
    cout << sol.strStr(hay, need) << endl;
}

 

这一类算法确实应该好好理解学习一下，提升了很大效率，这一块作为我的薄弱环节，应该继续努力。