📚 지식 노트

자리는 n − m + 1 = 8개, 비교 상한은 8 × 4 = 32번이다. 패턴이 본문 밖으로 삐져나가면 안 되므로 시작 위치는 0부터 7까지다. 실제로는 대부분 첫 글자에서 틀려 16번만 비교하고, 0번과 7번 자리에서 찾는다.

단순 탐색은 이미 맞춘 글자에서 아무것도 배우지 않는다. 그래서 두 칸 이상 건너뛰면 그 사이에 시작하는 일치를 놓칠 수 있다(예: AAAA에서 AA는 0, 1, 2번 세 자리에 겹쳐 나온다). 안전하게 크게 건너뛰려면 KMP처럼 패턴을 미리 분석해야 한다.

0번과 6번 자리에서 찾고, 비교는 17번이다. 자리 0부터 6까지의 비교 횟수는 4, 2, 1, 3, 2, 1, 4다. 찾은 자리는 네 글자를 다 비교하고, 틀린 자리는 맞은 글자 수 + 1번(틀린 글자까지) 비교한다.

AAAAAAAA는 20번, ABCDEFGH는 6번이다. AAAAAAAA에서는 다섯 자리 모두 AAA까지 맞고 마지막 B에서 틀려 자리마다 4번씩, (n − m + 1) × m = 5 × 4 = 20번이다. 이것이 O(nm) 최악이다.

ABCDEFGH에서는 0번 자리만 A가 맞아 2번, 나머지 네 자리는 첫 글자에서 틀려 1번씩이다. 보통의 글이 이쪽에 가까워서 단순 탐색이 실무에서 생각보다 빠르다. 반대로 같은 글자가 길게 반복되는 데이터(DNA, 0으로 채운 바이너리)에서는 최악에 가까워진다.

π[4] = 2다. ABCAB의 앞 AB와 뒤 AB가 같고, 세 글자(ABC와 CAB)는 다르다.

실패 함수는 진부분 문자열(자기 자신 전체는 뺀다)만 센다. π가 맞춘 길이 j와 같으면 틀렸을 때 패턴을 j − π = 0칸 밀게 되어 같은 비교를 끝없이 반복한다. 진부분으로 제한해야 틀릴 때마다 패턴이 적어도 한 칸 나아간다.

π = [0, 0, 1, 0, 1, 2, 3, 2]다.

i = 6까지는 앞에서 이어진다(ABA까지 맞아 k = 3). i = 7에서 p[7] = B와 p[3] = C가 달라 k를 π[2] = 1로 물린다. 이번에는 p[7] = B와 p[1] = B가 같아 k = 2가 되고, π[7] = 2다. 실제로 ABACABAB의 끝 AB가 앞 AB와 같고, 끝 ABAB는 앞 ABAC와 다르다.

ABCABCABC는 ABC의 세 번 반복이고, ABCABCAB는 어떤 짧은 단위의 정확한 반복도 아니다. 가장 짧은 주기는 m − π[m − 1]이다. 첫 문자열은 9 − 6 = 3이고 9가 3으로 나누어떨어지므로 ABC × 3이다.

둘째는 8 − 5 = 3으로 주기는 3이지만(세 칸 밀면 겹친다) 8이 3으로 나누어떨어지지 않아 ABC를 몇 번 이어 붙여도 정확히 만들어지지 않는다. 그래서 반복 단위는 문자열 자신(길이 8)이다. 주기 m − π[m − 1]이 m을 나눌 때만 반복이다.

본문 4번 글자(그대로)와 패턴 2번 글자를 비교한다. 맞춘 글자 수 j = 4의 실패 함수 값 π[3] = 2로 j를 되돌린다. 패턴을 4 − 2 = 2칸 밀어 2번 자리에 대는 것이고, 앞 AB는 본문 2~3번의 AB와 이미 맞는다는 것을 알기에 다시 보지 않는다.

π = [0, 1, 0, 1], 찾은 자리는 0과 6, 비교는 13번이다. 단순 탐색은 19번이다. 본문 5번의 C에서 세 번(B, A, A와) 비교하며 패턴이 물러나는 것이 가장 비싼 곳이다.

찾은 직후 j = π[3] = 2로 두고, 0·2·4번 자리에서 찾으며 비교는 8번이다. 본문 글자마다 딱 한 번씩 비교하고 끝난다. 찾은 ABAB의 끝 AB가 다음 일치의 앞 AB가 되기 때문이다.

j를 0으로 되돌리면 본문 4번부터 새로 맞추게 되어 2번 자리의 일치를 놓친다. 겹침을 허용하지 않는 찾기(예: 바꾸기 기능)라면 그때는 j = 0으로 두는 것이 맞다.

①은 참, ②는 거짓이다. 같은 글자열은 늘 같은 해시를 내므로 해시가 다르면 글자도 반드시 다르다. 그래서 해시가 다른 창은 글자를 보지 않고 넘긴다. 반대로 15, 37처럼 다른 수도 같은 나머지를 낼 수 있다(가짜 일치).

그래서 라빈-카프는 해시가 같을 때 반드시 글자를 직접 비교한다. 해시는 "다르다"를 빨리 판정하는 거름망이지 "같다"의 증거가 아니다.

창 해시는 9, 3, 8, 4, 4, 4, 4, 10, 9, 2이고, 가짜 일치는 3번(15, 59, 92)이다. 진짜 일치는 6번 자리의 26 하나다. 해시가 4인 창 네 개에서만 글자를 비교한다.

법이 11이면 해시 값이 11가지뿐이라 열 창 중 넷이 같은 값에 몰렸다. 실무에서 10⁹ 근처의 큰 소수를 법으로 쓰는 이유다.

해시는 8이다. 나가는 숫자의 자릿값은 10² mod 11 = 1이다. 새 해시 = ((9 − 1 × 1) × 10 + 5) mod 11 = 85 mod 11 = 8. 직접 계산한 415 mod 11 = 8과 같다.

뺄셈이 음수가 되면 법을 한 번 더해 양수로 맞춘다. 10² mod 11은 창 길이가 정해지면 한 번만 구해 두므로, 창 길이가 m이어도 한 칸 미는 비용은 곱셈·덧셈 몇 번인 O(1)이다. 다시 계산하면 O(m)이다.

편집 거리는 1(R 넣기)이고, 답은 오른쪽 아래 D[3][4]다. D[2][0]은 CA를 빈 문자열로 바꾸는 비용이라 두 글자를 지우는 2다. 0행·0열이 0, 1, 2…로 시작하는 까닭이다.

편집 거리는 3이다. 표의 마지막 줄은 [5, 4, 4, 3]이다. 되짚으면 H → R 바꾸기, R 지우기, E 지우기가 나온다(O와 S는 그대로 둔다).

표를 되짚을 때 대각선·위·왼쪽 중 같은 값으로 이어지는 이웃이 둘 이상이면 어느 쪽을 먼저 보느냐에 따라 다른 편집 순서가 나올 수 있다. 그래도 비용은 모두 3이다. 거리 값은 하나지만 최적의 편집은 여러 개일 수 있다.

TEH → THE는 2, TEH → TEA는 1이라 TEA를 추천한다. 레벤슈타인 거리에는 맞바꾸기가 없어서 두 글자가 뒤바뀐 오타(EH ↔ HE)를 바꾸기 두 번으로 센다.

이웃한 두 글자 맞바꾸기도 비용 1로 치는 다메라우-레벤슈타인 거리를 쓰면 TEH → THE도 1이 되어 두 후보가 같아진다. 그다음은 단어가 얼마나 자주 쓰이는지(빈도)로 THE를 고른다. 실제 검사기는 거리와 빈도, 자판에서 가까운 글자 같은 정보를 함께 쓴다.

순위 4와 5(na, nana)이고, na는 2번과 4번 위치에서 나온다. 사전순 정렬은 첫 글자부터 비교하므로, 앞 두 글자가 na인 문자열은 na보다 작은 것과 큰 것 사이의 한 구간에 모인다.

SA = [5, 1, 3, 0, 2, 4], LCP = [0, 1, 1, 0, 2, 0]이고, pa는 순위 3~4로 위치 0과 2에서 나온다. 사전순은 a, apaya, aya, papaya, paya, ya다.

apaya와 aya는 a만 같아 LCP 1, papaya와 paya는 pa가 같아 LCP 2다. 이진 탐색은 "앞 두 글자가 pa 이상인 첫 순위"(3)와 "pa보다 큰 첫 순위"(5)를 찾아 그 사이를 답으로 낸다.

가장 긴 반복은 mama(LCP 최댓값 4)이고, 서로 다른 부분 문자열은 11개다. 두 번 이상 나오는 부분 문자열은 두 접미사의 공통 접두사이고, 가장 긴 공통 접두사는 정렬에서 이웃한 쌍에 있으므로 LCP의 최댓값이 답이다.

부분 문자열은 모두 어떤 접미사의 접두사다. 접미사 길이의 합 n(n + 1)/2 = 21개 중, 바로 윗줄과 겹치는 접두사(LCP)는 이미 센 것이므로 뺀다. LCP 합은 0 + 1 + 3 + 0 + 2 + 4 = 10이라 21 − 10 = 11이다. mama는 위치 0과 2에서 서로 겹쳐 나온다.