아호-코라식 알고리즘

여러 패턴을 함께 찾기

본문 하나에 대해 패턴마다 검색을 반복하는 대신 패턴 집합을 미리 하나의 구조로 만든다. 예를 들어 패턴이 ab, bab, bc라면 겹치는 접두사를 트라이에서 공유할 수 있다. 본문을 읽을 때 현재 상태는 지금까지 읽은 끝부분 가운데 패턴의 접두사로 쓸 수 있는 정보를 나타낸다.

실패 링크의 역할

현재 상태에서 다음 문자로 바로 진행할 수 없을 때 실패 링크를 이용한다. 이 링크는 현재 문자열보다 짧은 접미사 중에서 트라이의 경로로 나타낼 수 있는 가장 긴 문자열의 상태로 이어진다. 이미 읽은 본문을 처음부터 되돌아가 비교하지 않고, 이어서 일치할 수 있는 짧은 후보를 유지하는 방식이다.

겹친 결과의 출력

본문이 bab일 때 패턴 bab뿐 아니라 끝의 ab도 일치한다. 현재 노드가 하나의 패턴 끝이라는 사실만 검사하면 이런 결과를 놓칠 수 있다. 실패 링크 쪽에 있는 패턴 끝도 출력 정보에 반영해야 한다. 겹치는 일치를 전부 찾을지, 겹치지 않는 일부만 선택할지는 별도의 결과 정책이다.

시간과 공간의 조건

전이와 실패 링크를 적절히 처리하면 길이 n인 본문을 검색하고 일치 결과 z개를 출력하는 데 O(n+z)이 걸린다. 출력 개수가 많으면 그 비용도 커진다. 전처리 시간과 메모리는 패턴 총길이뿐 아니라 문자 집합 크기와 전이를 배열로 저장할지 맵으로 저장할지에 따라 달라진다.