[Computer Algorithms] KMP Algorithm

https://www.youtube.com/watch?v=ynv7bbcSLKE&t=147s

 

영상에 소개된 것과 같이, O(m + n)에 text에서 pattern이 나타나는 인덱스를 찾는 알고리즘

 

import sys
read = sys.stdin.readline

def LPS(pattern):
    m = len(pattern)
    lps = [0] * m
    j = 0
    i = 1
    while i < m:
        if pattern[i] == pattern[j]:
            j += 1
            lps[i] = j
            i += 1
        else:
            if j != 0:
                j = lps[j - 1]
            else:
                lps[i] = 0
                i += 1
    return lps

def KMP(text, pattern):
    n = len(text)
    m = len(pattern)
    lps = LPS(pattern)
    i = j = 0
    while i < n:
        if pattern[j] == text[i]:
            i += 1
            j += 1
        if j == m:
            print("Pattern found at index:", i - j)
            j = lps[j - 1]
        elif i < n and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1

text = read().rstrip()
pattern = read().rstrip()
KMP(text, pattern)