UESTC 2459

发表于 更新于 分类于 ， ，

题目

给两段字符串$A$和$B$，输出$A$中所有出现$B$的位置。

题解

这题是老KMP了，不过还是说下怎么做吧不然太水了。

其实KMP可以看成是一个状态机，按照模式串（也就是要匹配的字符串，这里是$B$）建立状态转移，字符串作为输入。

理论上来说一个状态应该有多个转移方式，由当前状态（也就是匹配到的位置）和下一个字符来决定转移到哪个状态，但是为了方便，我们只取两种，即匹配成功和匹配失败，这样的简化与前面的那个方式基本上是等价的，这也就是next数组的由来，next[i]表示在第i位失配时模式串指针应该回退到的位置，而next数组本身的含义是“字符串的前缀与后缀相同的最大长度”，其中“前缀”指除了最后一个字符以外，一个字符串的全部头部组合，“后缀”指除了第一个字符以外，一个字符串的全部尾部组合。

另外一点，与普通的查找字符串不同的是，这题要求的是所有出现的位置，所以对于一个长度为$n$的模式串，在计算next数组的时候需要计算到第$n$位，也就是说在完全匹配（也就是模式串指针到达尾部）的时候模式串指针应该进行同样的跳转而不是回到0。

说实话对于KMP还是有一点迷糊，虽然知道它的原理，但总是觉得自己并没有真正理解。

代码

AC代码

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
// @author: hzy
//#pragma G++ optimize("O3")

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <list>
#include <forward_list>
#include <stack>
#include <unordered_set>
#include <vector>
#include <limits.h>

#define DISPLAY_A 0

using namespace std;

const int MAX = 1e6 + 7;

int nextt[MAX];

void getNext(string &p) {
    int len = p.length();
    nextt[0] = -1;
    int k = -1;
    int j = 0;
    while (j < len) {
        //p[k]表示前缀，p[j]表示后缀（并没有“真”！）
        if (k == -1 || p[j] == p[k])//j在这
        {
            j++;//j+1在这
            k++;//k=k+1
            //---->若p[k]=p[j]，则next[j+1]=next[j]+1;
            //下一个位置的next
            if (p[j] != p[k])//当p[k]！=p[j]时，与主串不匹配时可以返回到这
            {
                nextt[j] = k;
            } else//当p[j]=p[k]时与主串匹配时你在j位置不匹配匹配串返回这里当前
                //还是 不能与主串匹配，然后还是要返回next[]即next[next[k]]
                nextt[j] = nextt[k];//优化了
        } else {
            k = nextt[k];
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    string a, b;
    getline(cin, a);
    getline(cin, b);
    getNext(b);
    int j = 0;
    for (int i = 0; i < a.length();) {
        if (j == -1 || a[i] == b[j]) {
            j++;
            i++;
        } else {
            j = nextt[j];
        }
        if (j == b.length()) {
            // 匹配成功
            cout << i + 1 - j << " ";
            j = nextt[j];
        }
    }
    return 0;
}

测试例生成（Python）

1
2
3
4
5
6
7
8
9
def A(lenA, lenB, r=50, filename='in'):
    asciiSet = range(32, 126 + 1)
    a = "".join([chr(asciiSet[random.randint(32, 32 + r) - 32]) for x in range(lenA)])
    b = "".join([chr(asciiSet[random.randint(32, 32 + r) - 32]) for x in range(lenB)])
    f = open(filename, 'w')
    f.write(a)
    f.write("\n")
    f.write(b)
    f.close()

暴力验证

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
// @author: hzy
//#pragma G++ optimize("O3")

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <list>
#include <forward_list>
#include <stack>
#include <unordered_set>
#include <vector>
#include <limits.h>

#define DISPLAY_A 0

using namespace std;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    string a, b;
    getline(cin, a);
    getline(cin, b);
    for (int i = 0; i <= (int)(a.length() - b.length()); i++) {
        int c = 0, j = 0;
        while (j < b.length() && a[c + i] == b[j]) {
            j += 1;
            c += 1;
        }
        if (j == b.length()) {
            cout << i + 1 << " ";
        }
    }
    return 0;
}