算法训练营（day09）
KMP算法理论基础
什么是KMP
由这三位学者发明的：Knuth，Morris和Pratt，所以取了三位学者名字的首字母。所以叫做KMP
KMP有什么用
什么是前缀表
KMP中定义的 next数组 就是前缀表
前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配
所以前缀表就是：记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀 的数组
为什么一定要用前缀表
如动画所示，文本串中第六个字符 b 和 模式串的第六个字符 f 不匹配。如果暴力匹配，发现不匹配，此时就要从头匹配。但如果使用前缀表，就不会从头匹配，而是从上次已经匹配的内容开始匹配，找到了模式串中第三个字符 b 继续开始匹配，提高了查询效率
如何计算前缀表
计算前缀表之前，需要引入一个概念： 最长公共前后缀
- 前缀是指 不包含最后一个字符的所有以第一个字符开头的连续子串。
- 后缀是指 不包含第一个字符的所有以最后一个字符结尾的连续子串。
前缀表要求的就是 相同前后缀的长度
具体的前缀表计算可以看 帮你把KMP算法学个通透！B站（理论篇）
前缀表与next数组
next数组就是前缀表，但是很多实现都是把前缀表统一减一（右移一位，初始位置为-1）之后作为next数组。这并不涉及到KMP的原理，而是具体实现
使用next数组来匹配
以下我们以前缀表统一减一之后的next数组来做演示。有了next数组，就可以根据next数组来 匹配文本串 s，和模式串 t 了。
注意next数组是新前缀表（旧前缀表统一减一）。匹配过程动画如下：
时间复杂度分析
其中 n 为文本串长度，m 为模式串长度
因为在匹配的过程中，根据前缀表不断调整匹配的位置，可以看出匹配的过程是 O(n) ，之前还要单独生成next数组，时间复杂度是 O(m) 。
KMP算法的时间复杂度是 O(n+m)
暴力解法显而易见是 O(n × m)
所以KMP在字符串匹配中极大地提高了搜索的效率。
构造next数组
定义一个函数 getNext 来构建next数组，函数参数为 指向next数组的指针 和 一个字符串
方式一：前缀表统一 -1
1
2
3
4
5
6
7
8
9
10
11
12
13
| public void getNext(int[] next, String needle){
int j = -1;
next[0] = j;
for(int i = 1; i < needle.length(); i++){
while(j >= 0 && needle.charAt(j + 1) != needle.charAt(i)){
j = next[j];
}
if(needle.charAt(j + 1) == needle.charAt(i)){
j++;
}
next[i] = j;
}
}
|
方式二：单纯前缀表
1
2
3
4
5
6
7
8
9
10
11
12
13
| public void getNext(int[] next, String needle){
int j = 0;
next[0] = j;
for(int i = 1; i < needle.length(); i++){
while(j > 0 && needle.charAt(j) != needle.charAt(i)){
j = next[j - 1];
}
if(needle.charAt(j) == needle.charAt(i)){
j++;
}
next[i] = j;
}
}
|
使用next数组来做匹配
28.找出字符串中第一个匹配项的下标
题目链接：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
解题思路
解题过程：
- 本题可使用暴力解法逐个字符遍历查询
- 亦可使用 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
| class Solution {
public int strStr(String haystack, String needle) {
if (needle == null || needle.length() == 0){
return 0;
}
int hlen = haystack.length();
int nlen = needle.length();
if (hlen < nlen){
return -1;
}
char[] ch = haystack.toCharArray();
char[] cn = needle.toCharArray();
for (int i = 0; i <= hlen - nlen; i++){
int h = i, n = 0;
while (n < nlen && ch[h] == cn[n]){
h++;
n++;
}
if (n == nlen){
return i;
}
}
return -1;
}
}
|
解法二：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
| class Solution {
public int strStr(String haystack, String needle) {
if(needle.length() == 0){
return 0;
}
int[] next = new int[needle.length()];
getNext(next, needle);
int j = 0;
for(int i = 0; i < haystack.length(); i++){
while(j > 0 && needle.charAt(j) != haystack.charAt(i)){
j = next[j - 1];
}
if(needle.charAt(j) == haystack.charAt(i)){
j++;
}
if(j == needle.length()){
return i - needle.length() + 1;
}
}
return -1;
}
public void getNext(int[] next, String needle){
int j = 0;
next[0] = j;
for(int i = 1; i < needle.length(); i++){
while(j > 0 && needle.charAt(j) != needle.charAt(i)){
j = next[j - 1];
}
if(needle.charAt(j) == needle.charAt(i)){
j++;
}
next[i] = j;
}
}
}
|
解法三：前缀表统一 减一
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
| class Solution {
public int strStr(String haystack, String needle) {
if(needle.length() == 0){
return 0;
}
int[] next = new int[needle.length()];
getNext(next, needle);
int j = -1;
for(int i = 0; i < haystack.length(); i++){
while(j >= 0 && needle.charAt(j + 1) != haystack.charAt(i)){
j = next[j];
}
if(needle.charAt(j + 1) == haystack.charAt(i)){
j++;
}
if(j == needle.length() - 1){
return i - needle.length() + 1;
}
}
return -1;
}
public void getNext(int[] next, String needle){
int j = -1;
next[0] = j;
for(int i = 1; i < needle.length(); i++){
while(j >= 0 && needle.charAt(j + 1) != needle.charAt(i)){
j = next[j];
}
if(needle.charAt(j + 1) == needle.charAt(i)){
j++;
}
next[i] = j;
}
}
}
|
459.重复的子字符串
题目链接：https://leetcode.cn/problems/repeated-substring-pattern/description/
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
解题思路
解题过程：
- 本题可使用库函数
substring() 暴力判断
- 本题亦可使用 KMP算法 进行判断
详细代码
解法一：库函数暴力解法
1
2
3
4
5
6
| class Solution {
public boolean repeatedSubstringPattern(String s) {
String str = s + s;
return str.substring(1, str.length()- 1).contains(s);
}
}
|
解法二：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
| class Solution {
public boolean repeatedSubstringPattern(String s) {
if (s.equals("")) return false;
int len = s.length();
s = " " + s;
char[] chars = s.toCharArray();
int[] next = new int[len + 1];
for (int i = 2, j = 0; i <= len; i++) {
while (j > 0 && chars[i] != chars[j + 1]) j = next[j];
if (chars[i] == chars[j + 1]) j++;
next[i] = j;
}
if (next[len] > 0 && len % (len - next[len]) == 0) {
return true;
}
return false;
}
}
|
解法三：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
| class Solution {
public boolean repeatedSubstringPattern(String s) {
if(s.equals("")){
return false;
}
int len = s.length();
s = " " + s;
char[] cs = s.toCharArray();
int[] next = new int[len + 1];
for(int i = 2, j = 0; i <= len; i++){
while(j > 0 && cs[i] != cs[j + 1]){
j = next[j];
}
if(cs[i] == cs[j + 1]){
j++;
}
next[i] = j;
}
if(next[len] > 0 && len % (len - next[len]) == 0){
return true;
}
return false;
}
}
|
