KMP算法是什么？用Python实现

KMP算法是一种字符串匹配算法，它可以在不需要回溯的情况下快速地在文本串中查找模式串的位置。

以下是用Python实现KMP算法的代码：

def kmp(s, p):
    # 构建next数组
    j, k, n, m = 0, -1, len(s), len(p)
    next = [-1] * m
    while j < m - 1:
        if k == -1 or p[j] == p[k]:
            j, k = j + 1, k + 1
            next[j] = k
        else:
            k = next[k]
    
    # 在文本串中查找模式串
    i, j = 0, 0
    while i < n and j < m:
        if j == -1 or s[i] == p[j]:
            i, j = i + 1, j + 1
        else:
            j = next[j]
    if j == m:
        return i - m   # 返回模式串在文本串中的起始位置
    else:
        return -1     # 没有找到模式串

使用示例：

s = "ababcabcacbab"
p = "abcac"

idx = kmp(s, p)
print(idx)   # 输出: 5

相关问题

python实现kmp算法

KMP算法是一种用于字符串匹配的高效算法。下面是一个Python实现KMP算法的示例：

def kmp_search(text, pattern):
    # 构建部分匹配表
    def build_partial_match_table(pattern):
        table = [0] * len(pattern)
        prefix = 0
        suffix = 1
        while suffix < len(pattern):
            if pattern[prefix] == pattern[suffix]:
                prefix += 1
                table[suffix] = prefix
                suffix += 1
            elif prefix > 0:
                prefix = table[prefix - 1]
            else:
                table[suffix] = 0
                suffix += 1
        return table

    # 使用部分匹配表进行匹配
    def match_with_table(text, pattern, table):
        i = 0
        j = 0
        while i < len(text) and j < len(pattern):
            if text[i] == pattern[j]:
                i += 1
                j += 1
            elif j > 0:
                j = table[j - 1]
            else:
                i += 1
        if j == len(pattern):
            return True, i - len(pattern)
        else:
            return False, None

    # 调用辅助函数进行匹配
    table = build_partial_match_table(pattern)
    return match_with_table(text, pattern, table)

# 示例用法
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
result, index = kmp_search(text, pattern)
if result:
    print("Pattern found at index", index)
else:
    print("Pattern not found")

这段代码实现了KMP算法的核心逻辑。首先，通过`build_partial_match_table`函数构建部分匹配表，然后使用`match_with_table`函数进行匹配。最后，调用`kmp_search`函数进行字符串匹配。

kmp算法python实现

以下是KMP算法在Python中实现字符串匹配的步骤：

def kmp_match(main_str, pattern_str):
    # 计算next数组
    def get_next(pattern_str):
        next_arr = [-1] * len(pattern_str)
        i, j = 0, -1
        while i < len(pattern_str) - 1:
            if j == -1 or pattern_str[i] == pattern_str[j]:
                i, j = i + 1, j + 1
                next_arr[i] = j
            else:
                j = next_arr[j]
        return next_arr

    next_arr = get_next(pattern_str)
    i, j = 0, 0
    while i < len(main_str) and j < len(pattern_str):
        if j == -1 or main_str[i] == pattern_str[j]:
            i, j = i + 1, j + 1
        else:
            j = next_arr[j]
    if j == len(pattern_str):
        return True, i - len(pattern_str)
    else:
        return False, None

其中，`main_str`为主字符串，`pattern_str`为要查找的子串。函数返回值为一个元组，第一个元素为布尔值，表示是否找到子串；第二个元素为整数，表示子串在主字符串中的起始位置。