Python实现KMP算法执行随机字符模式搜索时触发TypeError问题求助

问题排查 #

你的代码存在三个可直接触发报错的问题：

• 随机字符串赋值错误：print()函数的返回值为None，你将print()的执行结果直接赋值给Chars变量，导致后续调用len(Chars)时触发NoneType无len方法的报错。
• 函数名大小写不匹配：你定义的函数名为大写开头的KMP，但main函数中调用时写的是小写的kmp，Python大小写敏感，第一个问题修复后会继续触发名称未定义的报错。
• 缺少模块导入：代码中使用了random.choice生成随机字符串，但开头没有导入random模块，运行时会触发模块未找到的报错。

修复后完整代码 #

import random

def KMP(Pattern, Chars):
    # 计算最长相等前后缀的长度，存入前缀表K
    K = [] 
    n = -1
    K.append(n)
    for k in range(1, len(Pattern) + 1):
        while n >= 0 and Pattern[n] != Pattern[k - 1]:
            n = K[n]
        n = n + 1
        K.append(n)
    
    # 执行字符串匹配
    m = 0
    for i in range(0, len(Chars)):
        while m >= 0 and Pattern[m] != Chars[i]:
            m = K[m]
        m = m + 1
        if m == len(Pattern):
            print(f"匹配成功：起始下标{i - m + 1}，结束下标{i}")
            m = K[m]

def main():
    Pattern = "abcba"
    letters = "abc"
    # 拆分字符串生成和打印逻辑，保证Chars存储的是生成的字符串
    Chars = ''.join(random.choice(letters) for i in range(1000))
    print(Chars)
    # 调用大小写匹配的KMP函数
    KMP(Pattern, Chars)

if __name__ == '__main__':
    main()

修复说明 #

• 拆分了随机字符串生成与打印的逻辑，先生成字符串赋值给Chars再单独打印，保证Chars存储的是合法字符串而非None
• 修正了函数调用的大小写，和定义的KMP函数名保持一致
• 补充了random模块的导入
• 优化了匹配结果的输出格式，可读性更强

内容的提问来源于stack exchange，提问作者sali