kmp找到全部的匹配的字符串

KMP算法可以用于查找一个字符串在另一个字符串中的全部匹配位置。

具体实现步骤如下：

1. 首先预处理模式串，得到next数组，表示当匹配失败时，模式串应该跳到哪个位置继续匹配。

2. 然后从左到右扫描文本串，同时从左到右扫描模式串，进行匹配。

3. 如果匹配成功，将匹配位置记录下来，并将模式串继续向右移动一位。

4. 如果匹配失败，则根据next数组跳到下一个匹配位置，重复步骤2。

5. 直到模式串扫描完毕，或者文本串扫描完毕。

6. 返回匹配位置列表。

下面是Python代码示例：

def kmp(text, pattern):
    n = len(text)
    m = len(pattern)
    next = get_next(pattern)
    i = 0
    j = 0
    result = []
    while i < n:
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == m:
                result.append(i - j)
                j = next[j-1]
        else:
            if j == 0:
                i += 1
            else:
                j = next[j-1]
    return result

def get_next(pattern):
    n = len(pattern)
    next = [0] * n
    i = 1
    j = 0
    while i < n:
        if pattern[i] == pattern[j]:
            j += 1
            next[i] = j
            i += 1
        else:
            if j == 0:
                next[i] = 0
                i += 1
            else:
                j = next[j-1]
    return next

示例输入：

text = "abcabcabcabcd"
pattern = "abc"

示例输出：

[0, 3, 6, 9]

说明：模式串"abc"在文本串"abcabcabcabcd"中出现的位置分别为0、3、6、9。