아호-코라식

주장. 각 패턴 p를 삽입한 후, root에서 p의 문자를 순서대로 따라간 경로의 끝 노드는 정확히 p를 나타낸다. Trie의 노드 집합은 패턴들의 서로 다른 접두사 집합 P와 일대일 대응한다.

증명. 삽입 중 k글자를 처리한 노드가 p의 길이 k 접두사를 나타낸다고 가정한다. 다음 문자 c의 간선이 있으면 해당 노드로 이동하고, 없으면 c를 붙인 접두사의 노드를 생성한다. 같은 노드에서 같은 문자로 나가는 간선은 하나이므로 동일한 접두사가 중복 생성되지 않는다. $k=0$인 root부터의 귀납법으로 주장이 성립한다. 따라서 끝 노드의 terminal에 ID를 저장하면 패턴의 종료 위치를 정확히 식별한다.

∎

주장. $v,F(v),F(F(v)),\ldots$를 방문하되 root를 한 번 방문하면 멈춘다. 이 사슬에는 $L(v)$의 접미사이면서 P에 속하는 문자열들이 길이의 내림차순으로 정확히 한 번씩 모두 나타난다.

핵심 성질. 같은 문자열의 두 접미사 x, y에 대해 $|x|\le |y|$이면 x는 y의 접미사이다. 두 문자열 모두 원래 문자열의 마지막 문자를 공유하고, x가 차지하는 마지막 $|x|$글자가 y 안에 포함되기 때문이다.

증명. v 자신은 가장 긴 후보이다. $v\ne \mathrm{root}$일 때 $q=F(v)$는 정의상 그다음으로 긴 후보이다. q보다 짧은 후보 x는 위 성질에 의해 $L(q)$의 proper suffix이다. 역으로 $L(q)$의 접미사는 $L(v)$의 접미사이므로, $L(q)$의 proper suffix 중 P에 속하는 후보 집합은 $L(v)$에서 v와 q를 제외한 후보 집합과 정확히 같다. depth에 대한 귀납법으로 누락이 없다. F를 따라갈 때 깊이가 엄격히 줄어 중복도 없으며, 유한 번 후 root에 도달한다. root의 자기 링크는 다시 따라가지 않는다.

∎

불변식. 본문 접두사 X를 읽은 상태 v는 X의 접미사 중 P에 속하는 가장 긴 문자열을 나타낸다.

기초. $X=\varepsilon$이면 상태는 root이므로 성립한다.

귀납 단계. 다음 문자 c를 읽은 뒤의 비어 있지 않은 후보는 yc 꼴이다. $yc\in P$이면 접두사 닫힘에 의해 $y\in P$이고, y는 X의 접미사이다. 불변식에 의해 $|y|\le |L(v)|$이며, 같은 X의 접미사이므로 y는 $L(v)$의 접미사이다. 따라서 보조정리 2의 사슬에 y가 존재한다. 역으로 그 사슬의 y에 실제 c 간선이 있으면 $yc\in P$이고 Xc의 접미사이다. 두 방향이 모두 성립하므로 후보 집합이 정확히 일치한다.

사슬은 길이 내림차순이므로 c 간선이 있는 첫 노드의 자식이 최장 후보이다. 끝까지 없으면 $\varepsilon$이다. 이 후보는 정의상 $\delta (v,c)$이므로 상태를 $\delta (v,c)$로 갱신하면 불변식이 보존된다. 특히 v에 실제 c 간선이 있으면 바로 그 자식이다.

$\delta$의 계산 규칙은 실제 간선이 있으면 그 자식, 없고 $v\ne \mathrm{root}$이면 $\delta (F(v),c)$, root에서도 없으면 root이다. 깊이가 감소하므로 재귀 규칙은 종료한다. 뒤의 정리에서 go 배열이 이 $\delta$와 같음을 보이면 구현의 탐색 정당성도 따라온다.

∎

주장. root가 아닌 v의 실제 자식 $u = \operatorname{next}[v][c]$에 대해 $\operatorname{fail}[u] = \operatorname{go}[\operatorname{fail}[v]][c]$이다.

수학적 점화식. $L(u)=L(v)c$의 비어 있지 않은 proper suffix 후보를 yc라 두자. $y\in P$이고 y는 $L(v)$의 proper suffix이다. 길이가 $|L(v)|$보다 작아야 yc가 $L(u)$ 자체가 아니기 때문이다. 보조정리 2에 의해 가능한 y는 $F(v)$부터의 사슬에 모두 있다. 역으로 이 사슬의 y에 c 간선이 있으면 yc는 $L(u)$의 proper suffix 후보이다. 따라서 정리 3의 $\delta$ 규칙을 적용하면 $F(u)=\delta (F(v),c)$이다. 비어 있지 않은 후보가 없을 때도 양쪽 모두 root이다.

BFS 구현에 대한 귀납법. 처음에 root의 go는 실제 자식 또는 root이므로 $\delta$와 같다. 깊이 1의 노드는 proper suffix가 $\varepsilon$뿐이므로 $\operatorname{fail}=\mathrm{root}$가 정확하다. 이제 BFS에서 v를 꺼내기 직전, v의 fail과 더 얕은 노드들의 go가 정확하다고 가정한다. $\operatorname{fail}[v]$는 더 얕으므로 그 전이표가 완성되어 있다. 실제 간선이 없는 $\operatorname{go}[v][c]$는 정리 3의 규칙으로, 실제 자식 u의 fail은 위 점화식으로 정확히 계산된다. 자식 u는 큐 뒤에 들어가므로 자신이 처리될 때 필요한 더 얕은 전이들이 먼저 완성된다. 모든 노드가 한 번 큐에 들어가므로 귀납법이 전체에 적용된다.

그러므로 최종 배열은 $\operatorname{fail}=F, \operatorname{go}=\delta$이다. root 자식을 일반 점화식에서 제외하는 것은 단순 구현 편의가 아니라 자기 자신을 proper suffix로 선택하지 않기 위한 조건이다.

∎

주장. 본문 위치 i에서 끝나는 패턴 ID는 현재 상태 v와 v의 실패 조상에 저장된 terminal ID들의 합집합이다.

증명. 위치 i에서 끝나는 패턴 p는 읽은 본문의 접미사이며 P에 속한다. 정리 3에 의해 $|p|\le |L(v)|$이고, 보조정리 2에 의해 p의 끝 노드는 v의 실패 사슬에 있다. 역으로 이 사슬의 terminal 노드 문자열은 읽은 본문의 접미사이므로 실제로 위치 i에서 끝난다.

존재 여부는 $\operatorname{has}[v]=(\operatorname{terminal}[v]\ne\varnothing)\lor\operatorname{has}[\operatorname{fail}[v]]$으로 계산한다. 깊이에 대한 귀납법으로 정확하다. output link는 terminal이 아닌 실패 조상만 건너뛰므로 출력 ID 집합을 바꾸지 않는다. 각 노드는 사슬에서 한 번만 방문하고 ID는 자신의 terminal에만 저장되므로 동일 ID·종료 위치를 중복 보고하지 않는다. 시작 위치는 $i-|p|+1$이다.

out 점화식도 확인. $f=\operatorname{fail}[v]$가 terminal이면 f가 가장 가까운 terminal 실패 조상이다. 아니면 첫 terminal은 f의 엄격한 실패 조상 중 가장 가까운 것이므로 $\operatorname{out}[f]$이다. $\operatorname{out}[\mathrm{root}]=-1$을 기초로 깊이에 대해 귀납하면 계산이 정확하다. 출력 시 v 자체를 먼저 검사하고 그 뒤 out을 순회해야, v가 terminal인 경우도 빠지지 않는다.

∎

주장. 탐색 중 상태 v에 도착한 횟수를 $\operatorname{visit}[v]$라 두면, 패턴 끝 노드 u의 등장 횟수는 failure tree에서 u의 서브트리에 속한 모든 v의 $\operatorname{visit}[v]$ 합이다.

왜 트리인가. root를 제외한 각 노드는 실패 부모를 정확히 하나 갖는다. 부모로 갈 때 깊이가 줄어 사이클이 없고 모든 노드가 root에 도달한다. 따라서 root 자기 링크를 제거한 간선들은 연결된 트리를 이룬다.

증명. 정리 5에 의해 u의 패턴이 종료 위치 i에서 등장할 필요충분조건은 u가 그 위치의 상태 v의 실패 조상인 것이다. 이는 v가 u의 failure-tree 서브트리에 있다는 조건과 같다. 각 본문 위치는 정확히 한 상태의 visit만 증가시키므로 서브트리 합은 각 등장을 정확히 한 번 센다. 겹치는 등장도 종료 위치가 다르므로 별도로 계산된다.

$\operatorname{fail}[v]$는 Trie 깊이가 더 작다. 따라서 Trie BFS 역순에서는 모든 failure-tree 자손의 누적이 조상보다 먼저 끝난다. $\operatorname{cnt}[\operatorname{fail}[v]]\gets\operatorname{cnt}[\operatorname{fail}[v]]+\operatorname{cnt}[v]$를 root를 제외한 모든 노드에 수행하면 서브트리 합이 완성된다.

∎

패턴 삽입은 총 M개 문자를 처리한다. V개 상태에서 $\sigma$개 전이를 각각 한 번 계산하므로 dense 배열 구성은 $O(M+V\sigma )$이다. next·go가 각각 $V\sigma$개 원소를 저장하고, terminal ID의 총 개수는 패턴 수 K이므로 추가 공간은 $O(V\sigma +K)$이다. 원본 입력과 시각화용 사본의 저장 비용은 제외한 값이다.

완성된 go를 사용하면 N개 본문 문자의 상태 이동은 $O(N)$이다. 각 위치에서 현재 노드를 한 번 검사하고, output link로 방문한 노드는 반드시 한 개 이상의 ID를 출력한다. 출력 수가 Z일 때 추가 방문 수는 Z 이하이므로 전체 탐색·출력은 $O(N+Z)$이다.

횟수 계산은 본문 순회 $O(N)$, 역순 누적 $O(V), K$개 패턴 결과 추출 $O(K)$이므로 $O(N+V+K)$이다. $\sigma$가 상수이고 $V\le M+1$이면 구성·출력까지 $O(M+N+Z)$이다. $\sigma$가 입력에 따라 증가하는 경우에는 $V\sigma$ 항을 생략할 수 없다.

실패 이동을 명시적으로 수행하는 탐색도 전이 조회가 $O(1)$이라면 총 $O(N)$이다. 한 문자 소비로 Trie 깊이는 최대 1 증가하고, 실패 이동마다 최소 1 감소한다. 깊이는 음수가 될 수 없으므로 실패 이동 총 횟수는 증가 횟수 $O(N)$를 넘지 않는다. 이 분석은 탐색 과정에 대한 것이며, 임의의 맵 기반 구성 방식에 그대로 적용되는 것은 아니다.

∎