KMP

模式串匹配算法

开门见山，先看算法：

kmp算法：

inline void KMP(char *s1,char *s2,int len1,int len2){ // KMP
	//s1 主串  ，len1 为 s1 长度 
	//s2 模式串，len2 为 s2 长度
    int i = 0, j = 0; //从0位开始匹配
    while (i < len1) {  //临界值
        if (j == -1 || s1[i] == s2[j]) //匹配成功，继续
            i++, j++;
        else
            j = next_[j]; //失配
        if (j == len2)
            printf("%d\n", i - len2 + 1), j = next_[j];
        // j==len2时，匹配成功；i-len2+1即为第一个字母的位置;匹配成功后，j置为next_[j]
    }                                                      
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

BBC ABCDAB ABCDABCDABDE为主串

ABCDABD为模式串

下面初步说明匹配形式：

通过图像我们不难发现，每次当模式串有一部分已经匹配的时候：

如果下一个位置不匹配，则模式串的位置并不一定像朴素算法只向后移动一个位置，而是移动到模式串最长前后缀匹配的位置（next[j]）：

给大家个例子：

字符串 abcdab
前缀的集合：{a,ab,abc,abcd,abcda}
后缀的集合：{b,ab,dab,cdab,bcdab}
那么最长相等前后缀就是 ab

模式串中每一个字符前的字符串都有最长相等前后缀（可能为0），而且最长相等前后缀的长度是我们移位的关键，所以我们单独用一个next数组存储子串的最长相等前后缀的长度。而且next数组的数值只与模式串本身有关。

所以next[i]=j,含义是：下标为i 的字符前的字符串最长相等前后缀的长度为j。

next[] 的求解算法：

inline void get_next(char *s2,int len2){ //传入模式串及其长度，求出next_数组
    // next_数组是从 S[0到i-1]前子串 的前缀后缀最大值
    int i = 0, j;
    next_[0] = j = -1;
    while (i < len2)
        if (j == -1 || s2[i] == s2[j]) //类似于KMP的匹配
            next_[++i] = ++j;
        else
            j = next_[j]; //失配
}
1
2
3
4
5
6
7
8
9
10

看了这些还不过瘾，那让我们来做一道模板题吧：

【模板】KMP字符串匹配

题目描述

给出两个字符串 $s_1$ 和 $s_2$，若 $s_1$ 的区间 $[l,r]$ 子串与 $s_2$ 完全相同，则称 $s_2$ 在 $s_1$ 中出现了，其出现位置为 $l$。
现在请你求出 $s_2$ 在 $s_1$ 中所有出现的位置。

定义一个字符串 $s$ 的 border 为 $s$ 的一个非 $s$ 本身的子串 $t$，满足 $t$ 既是 $s$ 的前缀，又是 $s$ 的后缀。
对于 $s_2$，你还需要求出对于其每个前缀 $s^{\prime }$ 的最长 border $t^{\prime }$ 的长度。

输入格式

第一行为一个字符串，即为 $s_1$。
第二行为一个字符串，即为 $s_2$。

输出格式

首先输出若干行，每行一个整数，按从小到大的顺序输出 $s_2$ 在 $s_1$ 中出现的位置。
最后一行输出 $|s_2|$ 个整数，第 $i$ 个整数表示 $s_2$ 的长度为 $i$ 的前缀的最长 border 长度。

样例 #1

样例输入 #1

ABABABC
ABA
1
2

样例输出 #1

1
3
0 0 1
1
2
3

提示

样例 1 解释

。

对于 $s_2$ 长度为 $3$ 的前缀 ABA，字符串 A 既是其后缀也是其前缀，且是最长的，因此最长 border 长度为 $1$。

数据规模与约定

本题采用多测试点捆绑测试，共有 3 个子任务。

• Subtask 1（30 points）：$|s_1|\le 15$，$|s_2|\le 5$。
• Subtask 2（40 points）：$|s_1|\le 10^4$，$|s_2|\le 10^2$。
• Subtask 3（30 points）：无特殊约定。

对于全部的测试点，保证 $1\le |s_1|,|s_2|\le 10^6$，$s_1,s_2$ 中均只含大写英文字母。

代码详解：

#include 
using namespace std;
int n, k, len1, len2;
const int N = 1e6 + 5;
int next_[N];
char s1[N];
char s2[N];
inline void get_next(char *s2,int len2){ //传入模式串及其长度，求出next_数组
    // next_数组是从 S[0到i-1]前子串 的前缀后缀最大值
    int i = 0, j;
    next_[0] = j = -1;
    while (i < len2)
        if (j == -1 || s2[i] == s2[j]) //类似于KMP的匹配
            next_[++i] = ++j;
        else
            j = next_[j]; //失配
}
inline void KMP(char *s1,char *s2,int len1,int len2){ // KMP
    int i = 0, j = 0; //从0位开始匹配
    while (i < len1) {  //临界值
        if (j == -1 || s1[i] == s2[j]) //匹配成功，继续
            i++, j++;
        else
            j = next_[j]; //失配
        if (j == len2)
            printf("%d\n", i - len2 + 1), j = next_[j];
        // j==len2时，匹配成功；i-len2+1即为第一个字母的位置;匹配成功后，j置为next_[j]
    }                                                      
}
void solve(){
    scanf("%s", s1);
    scanf("%s", s2);
    len1 = strlen(s1);
    len2 = strlen(s2);
    get_next(s2, len2);
    KMP(s1, s2, len1, len2);
    for (int i = 1; i <= len2; ++i)
        printf("%d ", next_[i]); //输出next_数组
}
int main(){
    //ios::sync_with_stdio(0);
    //freopen("in", "r", stdin);
    int t = 1;
    //cin>>t;
    while(t--)
        solve();
    return 0;
}


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

---

[BOI2009]Radio Transmission 无线传输

题目描述

给你一个字符串 $s_1$，它是由某个字符串 $s_2$ 不断自我连接形成的。但是字符串 $s_2$ 是不确定的，现在只想知道它的最短长度是多少。

输入格式

第一行一个整数 $L$，表示给出字符串的长度。

第二行给出字符串 $s_1$ 的一个子串，全由小写字母组成。

输出格式

仅一行，表示 $s_2$ 的最短长度。

样例 #1

样例输入 #1

8
cabcabca
1
2

样例输出 #1

3
1

提示

样例输入输出 1 解释

对于样例，我们可以利用 $\text{abc}$ 不断自我连接得到 $\text{abcabcabc}$，读入的 $\text{cabcabca}$，是它的子串。

规模与约定

对于全部的测试点，保证 $1<L\le 10^6$。

题目解析：

cabcabca

通过输出 next_[] 数组： -1 0 0 0 1 2 3 4 5

next_[i] = j 表示第 i 位置前最长公共前后缀的长度为 j 。

c 位置最长公共前后缀的长度为 0
a 位置最长公共前后缀的长度为 0
b 位置最长公共前后缀的长度为 0
c 位置最长公共前后缀的长度为 1
a 位置最长公共前后缀的长度为 2
b 位置最长公共前后缀的长度为 3
c 位置最长公共前后缀的长度为 4
a 位置最长公共前后缀的长度为 5

注意：字符串存储是从下标0开始的，所以 :

next_[1] 表示 a 前面的子串 {c} 最长公共前后缀的长度为 0 。
next_[2] 表示 b 前面的子串 {ca} 最长公共前后缀的长度为 0 。
next_[3] 表示 c 前面的子串 {cab} 最长公共前后缀的长度为 0 。
next_[4] 表示 a 前面的子串 {cabc} 最长公共前后缀的长度为 1 。

答案$N-next[N]$可以这样理解：

从字符串的某一处开始到串末，和串首到某一处是完全相等的，其中最长的就是最长公共前后缀。

#include
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int,int>> vpii;
#define all(a) a.begin(), a.end()
#define nl '\n'
#define debug() cout << "debug:"
const int inf = 0x3f3f3f3f;
const int maxn = 2e5+5;
int next_[maxn];//下标从1开始记录 next_[i]=j 表示第i个字符前最长公共前后缀的长度为j
char s[maxn];
int n;
inline void get_next(char *s2,int len2){ //传入模式串及其长度，求出next_数组
    // next_数组是从 S[0到i-1]前子串 的前缀后缀最大值
    int i = 0, j;
    next_[0] = j = -1;
    while (i < len2)
        if (j == -1 || s2[i] == s2[j]) //类似于KMP的匹配
            next_[++i] = ++j;
        else
            j = next_[j]; //失配
}
void solve(){
    cin >> n;
    cin >> s;
    get_next(s, n);
    // for (int i = 0; i <= n; i++)
    //     cout << next_[i] << " ";
    // cout << nl;
    cout << n - next_[n] << nl;
}

int main(){
    //ios::sync_with_stdio(0);
    //freopen("in", "r", stdin);
    int t = 1;
    //cin>>t;
    while(t--)
        solve();
    return 0;
}

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