匹配

# KMP

双指针：i(不后退)，j(在最长前缀匹配表中找到次大回退)；

案例：
a b a b a b z a b a b a b a
0 0 1 2 3 4 0 1 2 3 4 5 7 5(4+1)
1
2

最长前缀匹配表：

参考：如何更好地理解和掌握 KMP 算法? - 知乎 (zhihu.com) (opens new window)

int[] calculateMaxMathLengths(String pattern){
    int[] next = new int[pattern.length()];
    int j = 0;
    for(int i=1;i<pattern.length();i++){
        while(j>0 && pattern.charAt(j)!=pattern.charAt(i)){
            j = next[j-1];
        }
        if(pattern.charAt(j) == pattern.charAt(i)){
            j++;
        }
        next[i] = j;
    }
    return next;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

寻找所有匹配字符串的开头：

最浅显易懂的 KMP 算法讲解_哔哩哔哩_bilibili (opens new window)

List<Integer> search(String text,String pattern){
    List<Integer> ret = new ArrayList<>();
    int[] next = calculateMaxMathLengths(pattern);
    int j = 0;
    for(int i=0;i<text.length();i++){
        while(j>0 && pattern.charAt(j)!=text.charAt(i)){
            j = next[j-1];
        }
        if(pattern.charAt(j) == text.charAt(i)){
            j++;
        }
        if(j == pattern.length()){
            ret.add(i-pattern.length()+1);
            j = next[j-1];
        }
    }
    return ret;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 28. 找出字符串中第一个匹配项的下标 (opens new window)

class Solution {
    public int strStr(String haystack, String needle) {
        int[] next = calculateMaxMathLengths(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(haystack.charAt(i)==needle.charAt(j)){
                j++;
            }
            if(j==needle.length()){
                return i-needle.length()+1;
            }
        }
        return -1;
    }
    int[] calculateMaxMathLengths(String pattern){
        int[] next = new int[pattern.length()];
        int j = 0;
        for(int i=1;i<pattern.length();i++){
            while(j>0 && pattern.charAt(j)!=pattern.charAt(i)){
                j = next[j-1];
            }
            if(pattern.charAt(j) == pattern.charAt(i)){
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}

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

# 459. 重复的子字符串 (opens new window)

方法一：KMP

方法二：API

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        String ss = s+s;
        return ss.substring(1,ss.length()-1).contains(s);
    }
}

1
2
3
4
5
6

# 686. 重复叠加字符串匹配 (opens new window)

# 214. 最短回文串 (opens new window)

← 摩尔投票法字符串模拟→