kmp算法心得

KMP算法（Knuth-Morris-Pratt算法）是一种字符串匹配算法，用于在一个文本串S内查找一个模式串P的出现位置。该算法的时间复杂度为O(n+m)，其中n为文本串S的长度，m为模式串P的长度。

KMP算法的核心思想是利用已经匹配过的信息来避免从头再次匹配。具体实现中，我们定义一个next数组，next[i]表示当模式串中第i个字符与文本串中的某个字符不匹配时，下一次匹配模式串中的哪个字符。

KMP算法的实现步骤如下：

1. 对模式串P进行预处理，得到next数组；

2. 在文本串S中通过next数组匹配模式串P。

下面是KMP算法的核心代码（以匹配模式串P为例）：

def kmp(s, p):
    n, m = len(s), len(p)
    # 预处理next数组
    next = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and p[i] != p[j]:
            j = next[j-1]
        if p[i] == p[j]:
            j += 1
        next[i] = j
    # 匹配模式串
    j = 0
    res = []
    for i in range(n):
        while j > 0 and s[i] != p[j]:
            j = next[j-1]
        if s[i] == p[j]:
            j += 1
        if j == m:
            res.append(i-m+1)
            j = next[j-1]
    return res

KMP算法的时间复杂度为O(n+m)，空间复杂度为O(m)，其中n为文本串S的长度，m为模式串P的长度。KMP算法相比暴力匹配算法可以大大减少匹配次数，提高匹配效率。