def kmp(text, pattern):
    n, m = len(text), len(pattern)
    # 접두사와 접미사가 일치하는 위치를 계산합니다
    lps = compute_lps(pattern)
    # 패턴 문자열과 텍스트 문자열을 비교합니다
    i, j = 0, 0
    while i < n:
        # 겹치면 둘다 진행
        if pattern[j] == text[i]:
            i += 1
            j += 1
        # 겹치는 부분이 패턴의 길이와 같다면 해당 인덱스를 출력한다.
        if j == m:
            return i - j
        # 겹치는 부분이 끝났을 때 lps에 계산된 정도만 이동한다.
        elif i < n and pattern[j] != text[i]:
            if j != 0:
                j = lps[j-1]
            else:
                i += 1
    return -1

def compute_lps(pattern):
    m = len(pattern)
    # 접두사와 접미사가 일치하는 위치를 저장할 리스트를 초기화합니다
    lps = [0] * m
    len_lps = 0
    i = 1
    while i < m:
        # 겹치면 다음 문자도 같이 확인
        if pattern[i] == pattern[len_lps]:
            len_lps += 1
            lps[i] = len_lps
            i += 1
        # 겹치는게 끝나면 겹치기 시작했던 바로 그 전값으로 시작 001123에서 끝났으면 123 전의 1에서 시작
        # 이때, i는 변하지 않고 
        elif len_lps != 0:
            len_lps = lps[len_lps-1]
        else:
        # 겹치지 않고 len_lps도 0이라면 처음부터 일치하는 문자열을 또 찾아야한다.
            lps[i] = 0
            i += 1
    return lps