[7급 국가직 알고리즘 2024년 25번]

다음은 텍스트에서 패턴과 일치하는 문자열을 찾기 위한 KMP(Knuth Morris Pratt) 알고리즘에서의 전처리 과정을 구현한 파이썬 프로그램이다. 패턴이 abcbabca인 경우, 아래 표의 (가) ∼ (라)에 들어갈 숫자를 바르게 연결한 것은?

def preprocess(pn: str):
    pt = 1
    k = 0
    pi = [0] * (len(pn) + 1)
    pi[pt-1] = -1
    pi[pt] = 0
    while pt != len(pn):
        if pn[pt] == pn[k]:
            k += 1
            pt += 1
            pi[pt] = k
        elif k == 0:
            pt += 1
            pi[pt] = k
        else:
            k = pi[k]
    print(pi)
pattern = 'abcbabca'
preprocess(pattern)

i	0	1	2	3	4	5	6	7	8
pn[i]	a	b	c	b	a	b	c	a
pi[i]	-1	0	0	0	0	(가)	(나)	(다)	(라)

(가) (나) (다) (라)