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`为要查找的子串。函数返回值为一个元组，第一个元素为布尔值，表示是否找到子串；第二个元素为整数，表示子串在主字符串中的起始位置。