KMP算法

KMP

• KMP算法用来在文本串中匹配模式串，查找模式串出现的位置。
• KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。
• 需要用到next数组，即前缀表。前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。
  • 前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。
  • 后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。
• 前缀表：记录下标i之前（包括i）的字符串中，子串(s[0]至s[i])有多大长度的相同长度的前缀、后缀。

计算前缀表

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// i是后缀末尾，j是前缀末尾
void getNext(vector<int>& next, const string& s) {
    int j   = 0;
    next[0] = 0;
    // j指向前缀末尾位置，i指向后缀末尾位置
    for (int i = 1; i < s.size(); ++i) {
        while (j > 0 && s[i] != s[j]) {
            j = next[j - 1];
        }
        if (s[i] == s[j]) {
            ++j;
        }
        next[i] = j;
    }
}

字符串匹配

int strStr(string haystack, string needle) {
    int m = haystack.size();
    int n = needle.size();
    if (n == 0) return 0;
    if (m == 0 || n > m) return -1;

    vector<int> next(n, 0);
    getNext(next, needle);

    int j = 0;
    // j 是模式串的下标，i 是文本串的下标
    for (int i = 0; i < m; ++i) {
        while (j > 0 && haystack[i] != needle[j]) {
            // 遇到不匹配字符时，跳转到前一个字符的前缀表的记录位置
            j = next[j - 1];
        }
        if (haystack[i] == needle[j]) {
            // 字符匹配
            ++j;
        }
        if (j == n) {
            return i - n + 1;
        }
    }
    return -1;
}

// 可发现匹配过程与创建前缀表的过程相似
int main() {
    string s1 = "aabaabaafa";
    string s2 = "aabaaf";
    cout << strStr(s1, s2) << endl;
    system("pause");
}

参考内容

代码随想录、LeetCode 28题