KMP算法是字符串查找算法，可以在O(n)的时间复杂度寻找一个字符串内的所有指定子串

下面都按照这个示例进行介绍，在text里寻找pattern，它们的值如下

1
2

text    = ababcbababaaababcbababaa
pattern = ababa

根据pattern生成prefix table

prefix table是由pattern的每个前缀的公共前后缀长度组成，如下图

我们得到0, 0, 1, 2, 3，然后在前面添加-1，然后去掉最后一个数，得到-1, 0, 0, 1, 2，这个就是prefix table，具体Python代码如下

• 通过观察，我们已经判断了前a个字符“公共前后缀长度”为m，如果新的字符刚好等于第m+1个字符，则前a+1个字符的“公共前后缀长度”就为m+1。我们直接判断pattern[i] == pattern[prefix_table[i - 1]]即可

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

def generate_prefix_table(pattern):
    prefix_table = [0] * len(pattern)
    for i in range(1, len(pattern)):
        # 判断当前和第m+1个是否相等。第m+1个即idx为m，即是prefix_table[i - 1]
        if pattern[i] == pattern[prefix_table[i - 1]]:  
            prefix_table[i] = prefix_table[i - 1] + 1
        # 判断和第1个字符是否相等
        elif pattern[i] == pattern[0]:    
            prefix_table[i] = 1
        else:
            prefix_table[i] = 0 # 否则就是0
    prefix_table.insert(0, -1)
    prefix_table.pop()
    return prefix_table

KMP搜索

有了prefix table就可以开始搜索了

先看下如何使用prefix table，先看以下例子，在text里查找pattern

1. 首先依次匹配，直到匹配失败，如下图(i=4,j=4)

   1 2 3 4 5

   i ababcbababaaababcbababaa ababa j ❌

2. 根据prefix_table[j=4]=2，将pattern位置2对应到匹配失败的位置，也就是令j=2，如下图（i=4,j=2）

   1 2 3 4 5

   i ababcbababaaababcbababaa ababa j ❌

3. 继续匹配，依然失败，如下图（i=4,j=0），此时prefix_table[j=2]=0，则将位置0移动到匹配失败的位置

   1 2 3 4 5

   i ababcbababaaababcbababaa ababa j ❌

4. 继续匹配，依然失败，如下图（i=5,j=0），此时j==0，说明第一个字符都不匹配，则从后面开始匹配

   1 2 3 4 5

   i ababcbababaaababcbababaa ababa j ❌

5. 当前如下图（i=6,j=0），第一个匹配

   1 2 3 4 5

   i ababcbababaaababcbababaa ababa j ✅

6. 此时顺利匹配，当j=m-1时且匹配时，如下图（i=10,j=4），记录当前位置，即pattern开始位置，即j - i，如果需求只是查找第一个，则可以返回了

   1 2 3 4 5

   i ababcbababaaababcbababaa ababa j ✅

7. 如果需要继续匹配，则移动至如下位置，此时j=0,i=11

   1 2 3 4

   i ababcbababaaababcbababaa ababa 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

def kmp_search(text, pattern, prefix_table):
    i, j, n, m = 0, 0, len(text), len(pattern)
    
    indices = []
    
    while i < n:
        if text[i] == pattern[j]:
            if j == m - 1:
                  # 成功匹配一个pattern
                indices.append(i - j)
                j = 0
            else:
                # 正在匹配一个pattern，还没有匹配完成
                j += 1
            i += 1
        else:
            if j == 0:
                # 第一个字符就匹配失败
                i += 1
            else:
                # 中间字符匹配失败，按prefix_table移动
                j = prefix_table[j]
                
    return indices