特定字符串匹配

def kmp_search(text, pattern):
    def compute_prefix_function(p):
        m = len(p)
        pi = [0] * m
        j = 0
        for i in range(1, m):
            while j > 0 and p[j] != p[i]:
                j = pi[j - 1]
            if p[j] == p[i]:
                j += 1
            pi[i] = j
        return pi

    n, m = len(text), len(pattern)
    pi = compute_prefix_function(pattern)
    q = 0
    for i in range(n):
        while q > 0 and pattern[q] != text[i]:
            q = pi[q - 1]
        if pattern[q] == text[i]:
            q += 1
        if q == m:
            return i - m + 1
    return -1

# 示例用法
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
result = kmp_search(text, pattern)
print(f"Pattern found at index: {result}")