字符串匹配问题

给定字符串 s1s_1，以及模式串 s2s_2，求 s2s_2 在 s1s_1 内的所有出现位置。

一个很朴素的想法就是一位一位进行比较，复杂度 O(MN)O(MN)，M,NM,N 为两字符串长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const int N = 1e6+5;
char s1[N],s2[N];
void brute_force(){
    int l1 = strlen(s1);
    int l2 = strlen(s2);
    for(int i=0;i+l2<=l1;i++){
        bool flag=1;
        for(int j=0;j<l2;j++){
            if(s1[i+j]!=s2[j]){
                flag=0;break;
            }
        }
        if(flag)printf("match at %d\n",i);
    }
}

KMP 算法

然而，KMP 算法可以让我们在 O(M+N)O(M+N) 的时间复杂度内求出所有出现位置。（算法名字来源于三个发明者的姓名首字母）

其核心思想就是减少不必要的比较操作（一位一位跳太慢了，有时候我们可以比较了之后就一次跳好多位）

next 数组

next 数组代表一个下标失配后，可以直接跳过多少个字符。

next[i] 的定义为，模式串 s2s_2 的前缀 [1…i][1\ldots i] 中，相同的真前缀和真后缀最大长度。

来看一个例子：

那么这个 next 数组到底怎么用呢？

我们用两个指针 i，j，分别代表目前在查找的字符串和模式串里面的匹配位置。考虑现在匹配到 ABABA，最后一位的 A 失配。

接下来发生了什么事情呢？

  1. i 的位置保持不变
  2. j 的位置跳转到最后一位匹配的对应 next 值后一个位置（2+1=3）

这是什么意思呢？其实 ABAB 的最长相同的真前缀和真后缀长度是 2，即 AB 和 AB，这就代表我们现在匹配成功的 ABAB，其实最后两个字符已经是匹配好的下一个的开头了（而且最长就是 2，所以说一定是用重复的 AB）。所以我们已经匹配好了最后的两个 AB，而 j 的位置就跳到了匹配完 AB 的下一个，继续进行匹配。

再看一个例子：

如果第一个字符就失配了，我们直接将 i 后移一位。

综上我们可以写出代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void kmp(){
    int l1 = strlen(s1);
    int l2 = strlen(s2);
    int i=0,j=0;
    while(i<l1){
        if(s1[i]==s2[j]) i++,j++; // 匹配
        else if(j>0) j=nxt[j-1]; // 失配
        else i++; // 第一位就失配

        if(j==l2){// 匹配成功了
            printf("%d\n",i-j+1);
            j=nxt[j-1]; 
        }
    }
}

看到这里，有的小朋友就要问了：我看这里的 j 不是会往回跳吗？那万一疯狂往回跳，复杂度不就变成 O(nm)O(nm) 了吗？

事实上，如果仔细想一想，就能发现，j 每往回跳一次，就至少匹配一次（只有匹配的时候 j 增加了），最多匹配 nn 次，那么最多往回跳 nn 次。

因此，匹配的复杂度是 Θ(n)\Theta(n) 的。

求解 next 数组

接下来就只需要求出 next 数组了。

考虑从前一位的 next 数组递推。由于前一位的 next 数组已经保证了 [0..nxt[i-1]],[i-nxt[i-1]...i-1] 是相同的。

  1. s[nxt[i-1]+1] = s[i]

    如图，显然 nxt[i] = nxt[i-1]+1。

  2. s[nxt[i-1]+1] != s[i]

    我们尝试退而求其次，找一个比较短的部分公共前缀部分进行匹配。而其的最长的就是紫色这里的 nxt 数值，因此我们将已经匹配的长度减小到 1，然后再看是否可以匹配。（注意，这里的找一个比较短的部分的过程可以进行多次）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void cal_next(){
    int l2 = strlen(s2);
    nxt[0]=0; // 初始
    int i=1;
    int pre=0; // 目前已经匹配的前缀长度
    while(i<l2){
        if(s2[pre]==s2[i]){
            pre++; // 相等，匹配前缀多一位
            nxt[i++]=pre;
        }
        else{
            // 这时候已经无法再找到之前的任何公共前后缀了
            // 而且还失配了，那么就不存在公共前后缀
            if(pre==0) nxt[i++]=0; 
            // 这时候我们退而求其次，找一个小一点的以前的匹配前缀长度
            else pre=nxt[pre-1];
        }
    }
}

如何说明复杂度？观察 pre，不难发现 pre 最多只会增加 mm 次，所以也最多只会往回跳 mm 次。

完整代码

洛谷P3375 【模板】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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;


const int N = 1e6+5;
char s1[N],s2[N];
int nxt[N];

void cal_next(){
    int l2 = strlen(s2);
    nxt[0]=0; // 初始
    int i=1;
    int pre=0; // 目前已经匹配的前缀长度
    while(i<l2){
        if(s2[pre]==s2[i]){
            pre++; // 相等，匹配前缀多一位
            nxt[i++]=pre;
        }
        else{
            // 这时候已经无法再找到之前的任何公共前后缀了
            // 而且还失配了，那么就不存在公共前后缀
            if(pre==0) nxt[i++]=0; 
            // 这时候我们退而求其次，找一个小一点的以前的匹配前缀长度
            else pre=nxt[pre-1];
        }
    }
}

void kmp(){
    int l1 = strlen(s1);
    int l2 = strlen(s2);
    int i=0,j=0;
    while(i<l1){
        if(s1[i]==s2[j]) i++,j++; // 匹配
        else if(j>0) j=nxt[j-1]; // 失配
        else i++; // 第一位就失配

        if(j==l2){// 匹配成功了
            printf("%d\n",i-j+1);
            j=nxt[j-1]; 
        }
    }
}

int main(){
    scanf("%s%s",s1,s2);
    cal_next();
    kmp();

    int n = strlen(s2);
    for(int i=0;i<n;i++){
        printf("%d ",nxt[i]);
    }
    return 0;
}