접두·접미·LPS 배열 만들기

단순 탐색은 어떤 위치에서 몇 글자가 일치하다가 실패하면, 다음 위치에서 처음부터 다시 비교했습니다. 하지만 실패하기 전까지 일치한 글자들은 이미 무엇인지 알고 있습니다. 그 글자들은 pattern의 앞부분과 똑같기 때문입니다. 그렇다면 text를 다시 읽지 않고, pattern만 보고도 "다음에는 어디서부터 이어서 비교하면 되는가"를 미리 계산해 둘 수 있습니다. 이 글에서는 그 계산의 바탕이 되는 LPS 배열을 만듭니다. 다음 글의 KMP 알고리즘은 이 배열을 써서 text를 한 번만 훑고 탐색을 끝냅니다.

접두사와 접미사

문자열의 앞쪽에서 시작하는 연속 구간을 접두사(prefix), 뒤쪽에서 끝나는 연속 구간을 접미사(suffix)라고 합니다. ABAB의 접두사는 A, AB, ABA, ABAB이고, 접미사는 B, AB, BAB, ABAB입니다. 이 가운데 문자열 전체가 아닌 접두사를 진접두사(proper prefix)라고 합니다. 전체 문자열은 늘 자기 자신의 접두사이면서 접미사이므로, 의미 있는 겹침을 찾으려면 전체를 빼고 생각해야 합니다.

ABAB에서 진접두사이면서 접미사이기도 한 것은 AB 하나이고 길이는 2입니다. 앞의 두 글자와 뒤의 두 글자가 똑같다는 뜻입니다. 아래 그림은 같은 ABAB를 두 줄로 놓고 앞의 AB와 뒤의 AB를 묶어 보인 것입니다.

LPS 배열

pattern의 각 위치 i에 대해, 앞부분 pattern[0:i + 1]에서 진접두사이면서 접미사인 가장 긴 문자열의 길이를 lps[i]라고 하겠습니다. LPS는 longest proper prefix which is also suffix의 머리글자입니다. 이 값은 위치가 아니라 길이라는 점을 기억해 두는 것이 좋습니다. pattern ABABAC의 LPS 배열은 다음과 같습니다.

ABABA에서 진접두사 ABA와 접미사 ABA는 가운데 A를 함께 쓰며 겹쳐 있습니다. 접두사와 접미사가 서로 겹쳐도 상관없습니다. 마지막 ABABAC는 C로 끝나는데 C로 시작하는 진접두사가 없으므로 0입니다.

이 값이 탐색에 쓸모 있는 이유는 다음 글에서 자세히 보겠지만, 간단히 말하면 이렇습니다. text의 어느 곳에서 pattern의 앞 5글자 ABABA까지 일치하고 다음 글자에서 실패했다면, 방금 읽은 text의 마지막 세 글자는 ABA입니다. 이 ABA는 pattern의 앞 세 글자와 같으므로, 처음부터 다시 비교하지 않고 "pattern의 앞 3글자는 이미 일치했다"는 상태에서 비교를 이어 갈 수 있습니다. 그 3이 바로 lps[4]입니다.

하나씩 확인하면 느리다

정의대로 계산하는 가장 쉬운 방법은, 각 앞부분에 대해 가능한 길이를 모두 시도해 앞쪽과 뒤쪽이 같은지 비교하는 것입니다. 아래 코드에서 part는 i번째 글자까지의 앞부분이고, 안쪽 반복은 길이를 1부터 하나씩 늘려 가며 같을 때마다 best를 덮어씁니다. 짧은 길이부터 시도하므로 반복이 끝났을 때 남은 best가 가장 긴 겹침입니다. range(1, len(part))가 len(part) 자체를 빼는 것은 앞부분 전체는 진접두사가 아니기 때문입니다.

def naive_lps(pattern):
    result = []
    for i in range(len(pattern)):
        part = pattern[:i + 1]
        best = 0
        for length in range(1, len(part)):
            if part[:length] == part[-length:]:
                best = length
        result.append(best)
    return result


print(naive_lps("ABABAC"))

[0, 0, 1, 2, 3, 0]

part[-length:]는 끝에서 length글자를 자른 접미사입니다. 결과는 맞지만, 앞부분 m개마다 길이를 최대 m개 시도하고, 시도할 때마다 최대 m글자를 비교하므로 O(m³)까지 걸립니다. pattern이 길면 이 계산이 탐색보다 더 오래 걸릴 수 있습니다.

앞에서 구한 값을 이어서 늘린다

더 빠른 방법은 바로 앞 위치에서 구한 값을 다시 쓰는 것입니다. lps[i - 1]이 j라는 것은 pattern[0:i]의 앞 j글자와 뒤 j글자가 같다는 뜻입니다. 여기에 글자 pattern[i]가 하나 붙었을 때, 그 글자가 앞 j글자 바로 다음 글자인 pattern[j]와 같다면 같은 부분이 한 글자 늘어나므로 lps[i] = j + 1입니다. ABABA의 값 3에서 다음 글자 C를 붙일 때는 pattern[3]인 B와 비교하게 됩니다.

두 글자가 다르면 j글자짜리 겹침은 더 늘릴 수 없으므로, 그다음으로 긴 겹침을 찾아 다시 시도해야 합니다. 여기서 핵심이 되는 관찰이 있습니다. pattern[0:i]에서 j보다 짧은 겹침은, 길이 j인 앞부분 pattern[0:j] 안에서 진접두사이면서 접미사인 것이어야 합니다. 그 겹침의 앞쪽은 pattern[0:j]의 접두사이고, 뒤쪽은 pattern[0:i]의 접미사인데 그것은 다시 길이 j인 뒤쪽 부분, 곧 pattern[0:j]와 같은 문자열의 접미사이기 때문입니다. 그래서 다음 후보의 길이는 이미 구해 둔 lps[j - 1]입니다. 이렇게 j를 lps[j - 1]로 줄이며, 글자가 같아지거나 j가 0이 될 때까지 되풀이합니다.

ABABAC의 마지막 C에서 이 과정을 따라가 보겠습니다. j는 lps[4]인 3에서 시작하고, pattern[3]인 B와 C가 다르므로 j를 lps[2]인 1로 줄입니다. 다시 pattern[1]인 B와 C가 다르므로 j를 lps[0]인 0으로 줄입니다. j가 0이면 첫 글자 pattern[0]인 A와 비교하는데 이것도 C와 다르므로 lps[5]는 0입니다. j가 3에서 2를 건너뛰고 바로 1로 간 것은, ABABA에서 길이 2인 앞쪽 AB와 뒤쪽 BA가 달라 길이 2인 겹침이 처음부터 없기 때문입니다. 사슬은 이렇게 실제로 있는 겹침의 길이만 긴 것부터 차례로 알려 줍니다.

def prefix_function(pattern):
    lps = [0] * len(pattern)
    j = 0
    for i in range(1, len(pattern)):
        while j > 0 and pattern[i] != pattern[j]:
            j = lps[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        lps[i] = j
    return lps


for pattern in ["ABABAC", "AAAA", "ABCAB", ""]:
    print(pattern, prefix_function(pattern))

ABABAC [0, 0, 1, 2, 3, 0]
AAAA [0, 1, 2, 3]
ABCAB [0, 0, 0, 1, 2]
 []

lps[0]은 글자 하나짜리 앞부분이라 진접두사가 빈 문자열뿐이므로 늘 0이고, 반복은 i = 1부터 시작합니다. 변수 j는 반복이 시작될 때 lps[i - 1]의 값을 들고 있습니다. while 반복이 겹침을 줄여 가는 부분이고, 그 뒤의 if가 글자가 같을 때 겹침을 한 글자 늘리는 부분입니다. AAAA의 마지막 값이 4가 아니라 3인 것은 문자열 전체를 빼고 진접두사만 보기 때문입니다.

왜 맞는가

lps[i]가 길이 k인 겹침이라면, 그 겹침에서 마지막 글자를 뗀 k - 1글자는 pattern[0:i]의 진접두사이면서 접미사이고, 떼어 낸 마지막 글자 pattern[i]는 pattern[k - 1]과 같아야 합니다. 따라서 lps[i]의 후보는 pattern[0:i]에서 진접두사이면서 접미사인 길이들에 1을 더한 값뿐입니다. 그 길이들은 큰 것부터 lps[i - 1], lps[lps[i - 1] - 1], …로 이어지는 사슬에 빠짐없이 들어 있습니다. 앞에서 본 관찰에 따라, 가장 긴 겹침보다 짧은 겹침은 모두 그 가장 긴 겹침 안의 겹침이기 때문입니다.

코드는 이 사슬을 긴 것부터 차례로 시도해, 다음 글자가 맞는 첫 길이에서 멈춥니다. 긴 것부터 시도하므로 처음 맞는 길이가 가장 긴 답이고, 사슬에 없는 길이는 처음부터 후보가 아니므로 놓치는 것이 없습니다. 사슬 끝까지 맞지 않으면 j = 0에서 첫 글자와 비교해 1 또는 0을 적습니다.

반복이 두 겹인데도 O(m)인 이유

for 안에 while이 들어 있으니 O(m²)처럼 보이지만, 실제로는 O(m)입니다. j가 늘어나는 곳은 if 안의 j += 1뿐이고, 이것은 i마다 많아야 한 번이므로 전체 과정에서 j는 많아야 m - 1만큼 늘어납니다. 반면 while이 한 번 돌 때마다 j는 적어도 1씩 줄어듭니다. lps[j - 1]은 j보다 작기 때문입니다. j는 0보다 작아지지 않으므로, 전체 과정에서 줄어드는 양은 늘어난 양을 넘을 수 없고, while이 도는 횟수도 모두 합해 m - 1번을 넘지 못합니다.

한 위치에서 여러 번 되돌아가는 일은 있습니다. AAAAAAAAAB의 마지막 B에서는 j가 8에서 시작해 7, 6, …, 0까지 여덟 번 되돌아갑니다. 하지만 그 전까지 A가 이어지는 동안 j는 한 번씩만 늘어났으므로, 전체를 합치면 되돌아간 횟수가 늘어난 횟수를 넘지 않습니다. 이처럼 한 번의 비용은 클 수 있어도 전체 비용의 합으로 따지는 분석은 리스트의 append에서 본 분할상환 분석과 같은 생각입니다. 따라서 시간은 O(m), 배열을 저장하는 공간도 O(m)입니다.

정리

• 접두사는 앞에서 시작하는 구간, 접미사는 뒤에서 끝나는 구간이며, 진접두사는 문자열 전체가 아닌 접두사입니다.
• lps[i]는 pattern[0:i + 1]에서 진접두사이면서 접미사인 가장 긴 문자열의 길이입니다. 위치가 아니라 길이입니다.
• 다음 글자가 pattern[j]와 같으면 겹침을 한 글자 늘리고, 다르면 j를 lps[j - 1]로 줄여 그다음으로 긴 겹침에서 다시 시도합니다.
• 더 짧은 겹침은 모두 가장 긴 겹침 안의 겹침이므로, lps를 따라가는 사슬이 가능한 후보를 빠짐없이 차례로 줍니다.
• j는 전체에서 많아야 m - 1만큼 늘고 되돌아갈 때마다 줄어들므로, 반복이 두 겹이어도 전체 시간은 O(m)입니다.

연습 문제

1. LPS 배열 손으로 만들기

ABCAB의 LPS 배열을 손으로 구하세요.

2. 마지막 값이 4가 아닌 이유

AAAA의 LPS 배열에서 마지막 값이 4가 아니라 3인 이유는 무엇인가요? 4를 허용하면 탐색에서 어떤 문제가 생길까요?

3. 겹침이 줄었다 늘어나는 경우

ABACABAB의 LPS 배열을 구하세요. 마지막 B에서 j는 어떻게 바뀌나요?

다음 글 KMP의 실패 전이와 겹치는 일치에서는 이 배열을 써서 text를 되돌아가 읽지 않고 pattern이 나타나는 모든 위치를 찾습니다.