KMP算法笔记I ----- 先学会朴素算法

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