Knuth–Morris–Pratt

kmp.py

#!/usr/bin/python3

def make_pi(p):
    n = len(p)
    pi = [0] * n
    i = 0
    for j in range(1, n):
        while i > 0 and p[i] != p[j]:
            i = pi[i-1]
        if p[i] == p[j]:
            i += 1
        pi[j] = i
    return pi

def kmp(s, p):
    pi = make_pi(p)
    n = len(p)
    m = len(s)
    i = 0
    for j in range(m):
        while i > 0 and p[i] != s[j]:
            i = pi[i-1]
        if p[i] == s[j]:
            i += 1
        if i == n:
            yield j-i+1
            i = pi[i-1]

def main():
    s = "AABAACAADAABAABA"
    p = "AABA"

    print(s)
    for i in kmp(s, p):
        print(" " * i, p, sep="")

if __name__ == '__main__':
    main()