KMP 완전히 이해해보기 - 1

KMP 알고리즘에 대해 개인적으로 완전히 이해해보려고 한다. 일단 GET PI 함수 부터 구현하고 직접 고민해보며 이해해보기로 했다.

 

싸지방 컴퓨터는 껐다 키면 다 날아가므로 코드나 고민한 내용들을 적어보았다.

 

from collections import deque

def getprefix(s):
    prefix=[]
    print(s,"'s prefix is")
    for i in range(len(s)):
        prefix.append(s[i])
        print(''.join(prefix))
    print()

def getsuffix(s):
    suffix=[]
    print(s,"'s suffix is")
    for i in range(len(s)):
        suffix.append(s[~i])
        print(''.join(suffix[::-1]))
    print()

def getpinn(s): # 간단히 생각해본 O(N^2)

    le=len(s)

    pi=[0]*(le)

    ps=[]

    for i in range(le):
        ps.append(s[i])
        prefix=deque([])
        suffix=deque([])
        for j in range(len(ps)//2):
            suffix.appendleft(ps[~j])
            prefix.append(ps[j])
            #print(prefix,suffix)
            if prefix==suffix:
                pi[i]=j+1
    
    return pi

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


# 
#
# 원리파악
# if s==AABAA 라면
# le=5이고, j=0 pi=[0,0,0,0,0]
# 
# 첫 for 문 (i=1)
# while 문에서 j>0 불만족 하므로 바로 넘어감
# if 문에서 s[i]('A')==s[j]('A') 이므로 j+=1
# j=1 pi[j]=1 즉 pi[1]=1
# 
# i=2
# while 문에서 j>0 만족 s[i(2)] 와 s[j(1)] 비교 s[i]는 'B' 이고 s[j]는 'A' 이므로 다름
# while 문 조건 만족 j=pi[j-1] j=1이므로 j=pi[1-1] 즉 j=pi[0]=0 이다.
# j=0이 되고 while 문 탈출 s[i(2)]==s[j(0)] 'B'=='A' 이므로 False 다음으로 넘어감
# j=0 pi[2]=0 (값의 수정은 없었으나 pi[2]의 값이 다시 수정될 일이 없음)
# 
# i=3
# while 문에서 j>0 불만족
# if 에서 s[i(3)]==s[j(0)] 비교 'A'=='A' 만족하므로 j+=1
# j=1 pi[i(3)]=1
#
# i=4 
# while 문에서 j>0 만족(j=1) s[i(4)]==s[j(1)] 비교, 'A'=='A'이므로 불만족 if로 넘어감
# 위에서 보았듯이 s[i]==s[j] 만족 j+=1
# j=2 pi[i(4)]=2
# 
# 보면서 일차적으로 드는 생각
# i 값은 항상 증가하고 변하지 않음
# 만약 j>0 이고 s[i]==s[j] 라면 j+=1이 되면서 pi[i]=j가 됨
# 만약 문자열이 'aaaaa' 라면 [0,1,2,3,4] 일 것임
#
# 만약 문자열이 'AABAAC' 라면 [0,1,0,1,2,0] 일 것임
# i=5
# 현 상태 j=2 pi=[0,1,0,1,2,0]
# 일단 while 문에서 j>0 만족 s[i]는 'C' s[j]는 'B' s[i]!=s[j]가 참이므로 
# j=pi[j-1] 이전의 pi값 가져옴 j=pi[1]=1 s[j]는 이제 'A'임
# 하지만 여전히 s[i]('C')!=s[j]('A') 이므로 while 문 탈출 불가능
# j=pi[j(1)-1] j=pi[0]=0 따라서 while문을 탈출하게 되고 if 문도 s[i]!=s[j] 이므로 불만족
# 값의 변화 X 즉 pi[5]는 0
#
# 고민해보면서 든 생각
# AABAA 이렇게 해서 AA AA 가 일치했다. 누적 일치한 길이 2가 있고 
# 뒤에 한 글자가 추가된 다음에 다시 비교를 한다. 만약 또 일치한다면 ((AABAAB) 인경우)
# 누적 일치 길이는 3이 될 것이다 (j=3) 만약 일치하지 않는다면 한 칸 땡긴다.
# j는 즉 일치했던 prefix의 끝자리를 나타내는 것이다.
# j를 땡기면서 만약 s[i]와 s[j]가 같다면 prefix의 j번째와 suffix의 끝이 같다는 것이고
# 그렇다면 앞은 같은것이므로?? pi[i]=j+1이 되는 것이다.
#



s=input()

#getprefix(s)
#getsuffix(s)

print(getpi(s))