다음은 텍스트에서 패턴과 일치하는 문자열을 찾기 위한 KMP(Knuth… | [7급 국가직 알고리즘] 24년 1회차 기출문제 상세 페이지

다음은 텍스트에서 패턴과 일치하는 문자열을 찾기 위한 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
(가)
(나)
(다)
(라)
(가) (나) (다) (라)

1 1 1 1

1 2 3 1

1 2 3 0

3 3 3 0

(가)~(라)는 차례로 1, 2, 3, 1이다.
pi[i]는 패턴 앞 i글자에서 접두사와 접미사가 일치하는 최대 길이이다(pi[0] = -1).
pi[5]: abcba → a 일치 → 1
pi[6]: abcbab → ab 일치 → 2
pi[7]: abcbabc → abc 일치 → 3
pi[8]: abcbabca → 코드에서 pn[7]=a ≠ pn[3]=b라 k = pi[3] = 0으로 돌아간 뒤 pn[7] = pn[0] = a가 일치 → 1
1, 1, 1, 1은 (나)·(다)에서 일치 길이가 ab, abc로 늘어나는 것을 반영하지 않았다.
1, 2, 3, 0은 마지막 a가 첫 글자 a와 일치하는 것을 놓쳤다.
3, 3, 3, 0은 abcba의 접두사·접미사 일치가 a 하나뿐이라 (가)부터 맞지 않는다.