写一个字符串匹配算法

字符串匹配算法是用来在一段文本中查找特定模式字符串的位置。最基本的字符串匹配算法是朴素字符串匹配算法，它简单直观，但效率较低。下面将介绍一种效率较高的字符串匹配算法——KMP算法（Knuth-Morris-Pratt）。

KMP算法的核心思想是在不匹配时，根据已匹配部分的信息，尽可能地跳过一些不必要的比较位置，避免从头开始匹配。

KMP算法分为以下步骤：
1. 首先计算模式字符串的最长相同前后缀数组（next数组），这个数组用于记录模式字符串中每个位置之前字符串的最长相同前后缀的长度。
2. 当在文本字符串中发现不匹配时，利用next数组跳过尽可能多的字符。

具体实现KMP算法的步骤如下：
- 初始化两个指针i和j，分别指向文本字符串T和模式字符串P的开始位置。
- 当j = -1（即模式字符串的第一个字符就不匹配）或者T[i] == P[j]时，i和j都向前移动一位。
- 当j != -1且T[i] != P[j]时，根据next数组调整j的位置，而i保持不变。
- 若i移动到文本字符串的末尾，则表示匹配成功，返回模式字符串在文本中的起始位置。
- 若j移动到模式字符串的末尾还未匹配成功，则将i向前移动一位，j根据next数组调整。

以下是一个简单的KMP算法的伪代码实现：

function KMP(T, P):
    m = length(T)
    n = length(P)
    if n == 0:
        return 0
    next = computeNext(P)
    j = 0
    for i in range(0, m):
        while j > 0 and T[i] != P[j]:
            j = next[j - 1]
        if T[i] == P[j]:
            j = j + 1
        if j == n:
            return i - j + 1
    return -1

function computeNext(P):
    n = length(P)
    next = new array(n, 0)
    k = 0
    for q in range(1, n):
        while k > 0 and P[k] != P[q]:
            k = next[k - 1]
        if P[k] == P[q]:
            k = k + 1
        next[q] = k
    return next