P3375题目链接
做题过程
认识KMP
KMP算法的优点是可以在线性时间内在一个长字符串中查找一个短字符串，而不需要回溯。KMP算法的核心思想是利用一个部分匹配表（partial match table）来记录短字符串的前缀和后缀的匹配情况，从而避免重复比较已经匹配过的字符
部分匹配表
以ABAB为例子(这边的索引值不是单取出该位置的字符)
| 索引 |
字符 |
部分匹配值 |
| 0 |
A |
0 |
| 1 |
B |
0 |
| 2 |
A |
1 |
| 3 |
B |
2 |
按照步骤
- 索引0，即为 A ，没有前缀没有后缀,没有公共部分，所以部分匹配值为0
- 索引1，即为AB，前缀A，后缀B，没有公共部分，所以部分匹配值为0
- 索引2，即为ABA，前缀 A AB ，后缀 A BA，含有公共部分前缀A与后缀A，因为没有多组，所以最长部分匹配值为1
- 索引3，即为ABAB，前缀 A AB ABA，后缀 B AB BAB ，含有公共部分前缀AB与后缀AB，因为没有多组，所以最长部分的长度为2,所以其匹配值为2
小节
部分匹配值取决于$i$中前缀和后缀的公共部分中的最长公共部分的长度，也就是前缀和后缀公共的部分可能会含有多组
- 例如 AAAA ，$i=3$时,前缀
A AA AAA ，后缀A AA AAA ，可见有三个公共部分，但是其长度最长的公共部分为AAA,其部分匹配值为$3$
作用
部分匹配表的作用是在短字符串和长字符串不匹配时，可以快速地找到短字符串的下一个比较位置，从而避免重复比较已经匹配过的字符
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public static int[] getnext(String pattern) {
int n = pattern.length();
int[] pmt = new int[n];
int j = 0;
for (int i = 1; i < n; i++) {
while (j > 0 && pattern.charAt(j) != pattern.charAt(i)) {
j = pmt[j - 1];
}
if (pattern.charAt(j) == pattern.charAt(i)) {
j++;
}
pmt[i] = j;
}
return pmt;
}
|
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
| public static List<Integer> kmpSearch(String text, String pattern) {
List<Integer> list = new ArrayList<>();
int n = text.length();
int m = pattern.length();
int[] pi = getnext(pattern);
int j = 0;
for (int i = 0; i < n; i++) {
while (j > 0 && pattern.charAt(j) != text.charAt(i)) {
j = pi[j - 1];
}
if (pattern.charAt(j) == text.charAt(i)) {
j++;
}
if (j == m) {
list.add((i - m + 1));
j = pi[j - 1];
}
}
return list;
}
|
题解
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
| public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws Throwable {
String s1 = br.readLine();
String s2 = br.readLine();
int start = 0;
int times = s1.length() - s2.length() + 1;
for (int i = 0; i < times; i++) {
if (s1.startsWith(s2, start)) pw.println(start + 1);
start++;
}
for (int ans : kmpSearch(s1, s2)) pw.println(ans + 1);
for (int i : getnext(s2)) pw.print(i + " ");
pw.flush();
}
}
|
