KMP算法

2023

关于KMP算法中next数组的构建.

0 算法描述

核心：构建模式串的next数组.

next数组：next[j]表示当模式串str[j]与原字符串不匹配时，应该跳转的下标

等价于len数组：len[i]表示字符串str[0, i]中最长公共前缀后缀长度

1 代码

构建len数组

1
2
3
4
5
6
7
8
9
10
11
vector<int> buildNext(string& s) {
    int n = s.length();
    vector<int> len(n);
    for(int i = 1, j = 0; i < n; i++) {
        while(j > 0 && s[j] != s[i])
            j = len[j - 1];
        if(s[j] == s[i]) j++;
        len[i] = j;
    }
    return len;
}

一个完整的KMP算法示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int strStr(string haystack, string needle) {
        vector<int> len = buildNext(needle);
        int m = haystack.length(), n = needle.length();
        for(int i = 0, j = 0; i < m; i++) {
            while(j > 0 && haystack[i] != needle[j])
                j = len[j - 1];
            if(haystack[i] == needle[j]) j++;
            if(j == n) return i - n + 1;
        }
        return -1;
    }
    
    vector<int> buildNext(string& s) {
        int n = s.length();
        vector<int> len(n, 0);
        for(int i = 1, j = 0; i < n; i++) {
            while(j > 0 && s[j] != s[i])
                j = len[j - 1];
            if(s[j] == s[i]) j++;
            len[i] = j;
        }
        return len;
    }
};

参考

[1] 什么是KMP算法(详解)