kmp

kmp实际上是对字符串匹配的优化算法.

对于字符串s和字符串 p, 要找到 p 在 s 中的位置, 那么暴力算法是以字符串的每个字符作为起点, 然后逐个比较 p 和 s 的字符, 若p的字符遍历完都是相等的, 那么说明我们找到了p 在 s 中的位置

暴力算法的时间复杂度是O(mn), m n 为两个字符串的长度

在整个过程中, 匹配到某一个字符 c 失败时, 那么在 c 之前很有可能有已经匹配的子串, 这部分子串是很重要的信息, 但是在暴力算法中完全忽略了, 在 kmp 中, 我们可以利用这部分已经匹配的子串来找到我们下一次应该遍历的起点, 这就优化掉了暴力算法中总是从 p 的开头开始匹配的缺陷.

具体做法如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


const int N = 100010;
const int M = 1000010;
char p[N], s[M];
int main(){
    int n, m;
    cin >> n >> p + 1 >> m >> s+1;
    int ne[N];
    for(int i = 2, j = 0; i <= n; i++) {
        while(j > 0 && p[i] != p[j + 1]) j = ne[j];
        if(p[i] == p[j + 1]) j++;
        ne[i] = j;
    }
    
    for(int i = 1, j = 0; i <= m; i++) {
        while(j > 0 && s[i] != p[j+1]) j = ne[j];
        if(s[i] == p[j+1]) j++;
        if(j == n) {
            j = ne[j];
            printf("%d ", i - n);
        }
    }
    return 0;
}

极简版本:

注释版本:

j 始终从 0 开始, 我们利用 j+1 来进行下一个位置的预判匹配, 匹配成功才让 j++

整个过程中, 只有 j 能退

$$ne[i]$$ 数组的定义:数组 $$p[1,i]$$ 的最长前后缀长度( 注意 1 为数组第一个元素)

前后缀指的是小于当前字符串长度的前后缀

 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
27
28
29
30
31
32
33
34
35


const int N = 100010;
const int M = 1000010;

char p[N], s[M];

int main(){
    int n, m;
    cin >> n >> p + 1 >> m >> s+1;
    int ne[N];
    for(int i = 2, j = 0; i <= n; i++) {
        //注意是 j+1 来预判
        while(j > 0 && p[i] != p[j + 1]) j = ne[j];
        //经过 while 循环之后, 如果一直不相等, 那么 j 会回到 0 位置, 此时 while 就没法帮助继续回退了
        //应该在新的 if 中预判下一个字符是否匹配, 所以不能无脑 j++
        if(p[i] == p[j + 1]) j++;
        ne[i] = j;
    }
    
    for(int i = 1, j = 0; i <= m; i++) {
        //注意是 j+1 来预判
        while(j > 0 && s[i] != p[j+1]) j = ne[j];
        //当不匹配的情况都回退之后, 我们还需要手动给j右移一位加一
        //注意是 j+1 来预判
        if(s[i] == p[j+1]) j++;
        if(j == n) {
            //让 j 回到上一次匹配的位置, 利用之前的最长真前后缀(真前后缀长度必小于n)再次进行匹配, 
            //如果之后还是匹配成功了, 那么j++还是有可能回到j==n的情况, 此时就可无限匹配后面的字符串
            j = ne[j];
            //如果打印语句 j = ne[j];之前, 那么在这里 i-n 和 i-j 都一样, 用哪个都行, 但是现在我们先写了 j = ne[j]; 所以这里只能是 i-n, 这里更推荐先写 j=ne[j], 因为打印并非所有题目都需要, 但是j = ne[j];却是不可少的
            printf("%d ", i - n);
        }
    }
    
    return 0;
}

这里说一下不能无脑 j++两个 case:

case1: while 循环帮助我们把 j 回退到了 p 字符串中间位置, 因为 while 循环没有让 j++能能力, 所以需要我们主动加一

case2: while 循环帮我们把 j 回退到了 p 字符的起始位置, 那么说明$$p[1,i]$$此时没有公共前后缀了, 但是 while在 j==0 的时候就退出了, 那么这个时候我们还是需要手动预判字符是否匹配, 不匹配那么就可以让 j 一直处在起始位置而不需要移动, 直到能预判成功才移动

题目: KMP字符串

找出字符串中第一个匹配项的下标

题外话

因为我们现在是从下标为 1 开始, 但是在一些时候我们会直接得到一个完整的数组, 这个时候可以使用std::copy(arr.begin(), arr.end(), targetArr+targetStartIndex) 来把数组的值复制到 p 数组或者 s 数组

arr 是我们一开始就有的数组, 在 c++中, 数组有 begin() end() 方法

begin()方法返回的是一个 iterator, 该 iterator 指向数组第一个元素 end()方法返回的是一个 iterator, 该 iterator 指向数组最后一个元素

应用举例:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


int main() {
    std::string s = "Hello, World!";
    char ch[1000] = {0}; // 初始化为全0
    int startIdx = 1; // 开始的索引位置

    // 确保不会溢出数组的边界
    if (startIdx + s.length() < sizeof(ch)) {
        std::copy(s.begin(), s.end(), ch + startIdx);
    }
    // 打印结果
    std::cout << ch << std::endl; // 注意：如果 ch[startIdx-1] 不是 '\0'，cout结果可能不正确, 但是在空间足够的情况下数组的值肯定是复制过去了
    return 0;
}

由于我们从索引 1 开始写入，而 char 数组的起始位置（索引 0）被初始化为零 (\0)，所以 cout 在输出字符数组时会从第一个非零的字符开始，直到下一个零字符为止。这意味着虽然整个字符串被复制到了数组中，但是 std::cout 只会打印从索引 1 开始的字符串。如果这不是你想要的行为，你需要将数组的第一个元素设置为一个空字符（’\0’），以便正确打印。