算法分析

参考:阮一峰

问题分析

问题:在字符串S = "BBC ABCDAB ABCDABCDABDE"中查询是否存在P = "ABCDABD"

按照字符串匹配的步骤可以得到这个中间步骤:

图1

到了这一步,按照暴力算法,是将搜索词整个后移一位,再从头逐个比较。这样做虽然可行,但是效率很差,因为你要把"搜索位置"移到已经比较过的位置,重比一遍。如下:

图2

那么换一个思路,不把搜索位置移动回去,而是移动搜索词,让搜索位置可以继续往后移动,这样的效率会高很多。这也是KMP算法的思路:

图3

那么问题就转变成了怎么确定搜索词的移动距离

讨论这个问题,要先知道几个概念:

1
2
3
4
5
6
7
8
9
10
11
12
13
前缀:除了最后一个字符以外,该字符串的全部头部组合

后缀:除了第一个字符以外,该字符串的全部尾部组合

部分匹配表:一个字符串的前缀和后缀的最长公有元素的长度

i : 数组的下标

ne[i] : 以i为结尾的部分匹配的值,ne数组即为部分匹配表。有性质:ne[1] = 0, ne[i] < i

ne[i] = j 含义:以 i 为结尾长度为 j 的字符串等于从1开始长度为 j 的字符串,
即p[1 ~ j] == p[i - j + 1 ~ i],
即以i为结尾的子串的最大公共元素长度为j,j即为最大公共元素长度

来看字符串ABCDABD

那么可以得到下面这张表:

P[] A B C D A B D
i 1 2 3 4 5 6 7
ne[i] 0 0 0 0 1 2 0

"部分匹配"的实质是,有时候,字符串头部和尾部会有重复。比如,“ABCDAB"之中有两个"AB”,那么它的"部分匹配值"就是2("AB"的长度)。搜索词移动的时候,第一个"AB"向后移动4位(字符串长度-部分匹配值),就可以来到第二个"AB"的位置。

代码分析

接下来具体看看ne数组怎么求:(类似于对自己做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
// s[]是长文本,p[]是搜索词,下标都是从1开始,n是s的长度,m是p的长度
for(int i = 2, j = 0; i <= m; i++) {
// (1)当共有元素长度不为0且下一个字母不匹配的时候,向后移动p串,即从图1移动到图3
while(j && p[i] != p[j + 1]) j = ne[j];

// (2)如果下一个字母匹配成功,那么共有元素长度+1,记录ne值
if(p[i] == p[j + 1]) {
j++;
ne[i] = j;
}

// (3)否则说明没有共有元素
else ne[i] = 0;
}

用上面的例子来模拟一遍求ne的过程:
A B C D A B D (ne[1]默认为0)
i = 2时,字母为B,j == 0,尝试匹配共有共有元素为1 (j = 0 + 1)的情况,得到p[i] != p[j + 1],执行(3)
同字母C,D
i = 5,字母A,j == 0,尝试匹配j = 0 + 1,得到p[i] == p[j + 1],执行(2)
同字母B
最后匹配字母D,执行(1),j = ne[j],之前j == 2,执行之后j = 0,来看看这个语句字母理解:
ne:0 0 0 0 1 2
A B C D A B|D| ---> A B C D A B|D|
A B|C|D A B D |A|B C D A B D
匹配失败,按照KMP算法,往后移动p串,原本j == 2,而ne[j] = 0(前两个字母的最大公共元素长度为0),所以移动之后j == 0

接下来就是做匹配的过程:(一样的做法)

1
2
3
4
5
6
7
8
for(int i = 1, j = 0; i <= n; i++) {
while(j && s[i] != p[j + 1]) j = ne[j];
if(s[i] == p[j + 1]) j++;
if(j == m) {
// 匹配成功后的逻辑
j = ne[j]; // 继续往后匹配
}
}

代码模板

简单优化一下求ne的算法,可以得到模板:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// s[]是长文本,p[]是搜索词,下标都是从1开始,n是s的长度,m是p的长度
// 求搜索词的ne数组:
for(int i = 2, j = 0; i <= m; i++ ) {
while(j && 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 <= n; i ++ ) {
while(j && s[i] != p[j + 1]) j = ne[j];
if(s[i] == p[j + 1]) j ++ ;
if(j == m) {
// 匹配成功后的逻辑
j = ne[j];
}
}

题目

来源:AcWing

给定一个模式串S,以及一个模板串P,所有字符串中只包含大小写英文字母以及阿拉伯数字。

模板串P在模式串S中多次作为子串出现。

求出模板串P在模式串S中所有出现的位置的起始下标。

输入格式

第一行输入整数N,表示字符串P的长度。

第二行输入字符串P。

第三行输入整数M,表示字符串S的长度。

第四行输入字符串S。

输出格式

共一行,输出所有出现位置的起始下标(下标从0开始计数),整数之间用空格隔开。

数据范围

1≤N≤105
1≤M≤106

输入样例

1
2
3
4
3
aba
5
ababa

输出样例

1
0 2

代码

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
#include<iostream>
using namespace std;

const int N = 10010, M = 100010;

int n, m;
int ne[N];
char s[M], p[N];

int main() {
cin >> n >> p + 1 >> m >> s + 1;
for(int i = 2, j = 0; i <= n; i ++) {
while(j && 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 && s[i] != p[j + 1]) j = ne[j];
if(s[i] == p[j + 1]) j++;
if(j == n) {
printf("%d ", i - n);
j = ne[j];
}
}

return 0;
}