第一次学习KMP算法走了不少弯路,下面老高按照自己的学习步骤,总结一下KMP算法的要点,如果有错误或者疑问,欢迎指正!

老高使用python语言实现算法,实现的语言不重要,重要的是他的思想!(其实老高的C语言早已年久失修?)

本文是系列的第一篇,学习KMP之前最好了解一下朴素算法的写法,为以后的学习最好铺垫,此为渐进式学习!

一些约定

  • 函数查找不到返回-1,最好支持全局搜索
  • s(string) 代表 需要匹配的字符串
  • t(target) 代表 我们想要查找的字符串
  • i 代表查找string时的下标
  • j 代表匹配target时的下标
  • k 代表next数组时最大前缀后缀的长度
  • next(next) 代表 next数组

查找字符朴素算法

朴素算法的内容很简单,s和t用笨办法比较,计算时我们只需要搞清楚i和j的位置即可完成匹配

def native(s, t):
    # 初始化长度
    s_len = len(s)
    t_len = len(t)
    # 初始化游标
    i = 0
    j = 0
    # 当遍历完s或者t完全匹配到时,停止循环
    while i < s_len and j < t_len:
        # 当准备考试匹配时检查剩下需要匹配的字符串长度是否足够比较
        # 如果长度不足时停止匹配
        if j == 0 and s_len - i < t_len:
            break

        if s[i] == t[j]:
            # 如果s的i和t的j相等,继续比较
            i = i + 1
            j = j + 1
        else:
            # 如果不相等,把i置为已经比较过的位置的下一个继续比较
            i = i - j + 1
            j = 0

        if j == t_len:
            return i - j

    return -1

我们还可以顺手把它改为查找全部:

def native_all(s, t):
    # 初始化长度
    s_len = len(s)
    t_len = len(t)
    # 初始化游标
    i = 0
    j = 0
    index = []
    # 当遍历完s或者t完全匹配到时,停止循环
    while i < s_len and j < t_len:
        # 当准备考试匹配时检查剩下需要匹配的字符串长度是否足够比较
        # 如果长度不足时停止匹配
        if j == 0 and s_len - i < t_len:
            break

        if s[i] == t[j]:
            # 如果s的i和t的j相等,继续比较
            i = i + 1
            j = j + 1
        else:
            # 如果不相等,把i置为已经比较过的位置的下一个继续比较
            i = i - j + 1
            j = 0
        # 如果发现j自增后于t的长度相等,说明匹配成功
        if j == t_len:
            # 放到index中,然后继续匹配,此时i
            index.append(i - j)
            j = 0

    return index