아호–코라식 다중 패턴 검색 계산기

패턴 여러 개를 한 번에 찾는 문자열 검색 알고리즘입니다. 1975년 알프레드 아호와 마거릿 코라식이 발표했으며, 패턴들을 트라이로 쌓은 뒤 어긋났을 때 돌아갈 자리를 미리 이어 둡니다. 패턴이 몇 개든 텍스트를 한 번만 지나가므로 O(패턴 길이 합 + 텍스트 길이 + 찾은 개수)에 끝납니다.

KMP의 실패 함수를 트라이 위로 올린 것이 아호–코라식입니다. KMP는 패턴 하나에 대해 「어긋나면 패턴의 어디로 돌아갈지」를 미리 적어 두는데, 아호–코라식은 그 실패 함수를 여러 패턴을 쌓은 트라이의 모든 노드에 붙입니다. 패턴이 하나뿐이면 아호–코라식은 사실상 KMP와 같습니다.

지금까지 읽은 글자의 진짜 접미사이면서 트라이에 있는 가장 긴 것을 가리킵니다. she까지 읽고 다음 글자가 어긋났다면 처음부터 다시 읽는 대신 he로 돌아가 이어 볼 수 있습니다. 너비 우선으로 훑으면 부모의 실패 링크가 이미 정해져 있으므로 자식의 실패 링크는 부모의 것을 따라가며 한 번에 정해집니다.

한 패턴이 다른 패턴의 접미사일 때 짧은 쪽을 놓치지 않기 위해서입니다. he, she, his, hers를 찾을 때 ushers를 읽으면 hers가 끝나는 자리에서 he도 함께 끝나는데, 트라이 노드에 적힌 패턴만 보면 he를 놓칩니다. 그래서 실패 링크를 따라가며 만나는 「패턴이 끝나는 노드」를 미리 이어 두고, 매치가 나올 때마다 그 사슬을 끝까지 따라갑니다. 이 알고리즘에서 가장 자주 틀리는 자리입니다.

텍스트를 훑는 횟수는 그대로입니다. 패턴 수는 오토마타를 만드는 비용(패턴 길이의 합)에만 들어가고, 검색 자체는 텍스트 길이와 찾은 개수에만 비례합니다. 패턴마다 따로 검색하면 패턴 수 × 텍스트 길이가 되므로, 금칙어 필터처럼 찾을 것이 수백 개일 때 차이가 크게 벌어집니다.

모두 찾습니다. aba와 ababa를 ababa에서 찾으면 aba가 0번과 2번 자리에서 두 번, ababa가 0번 자리에서 한 번 나옵니다. 겹치는 것을 빼고 세는 것은 찾은 뒤에 고를 문제이며, 알고리즘 자체는 끝나는 자리마다 모두 알려 줍니다.

전송되지 않습니다. 오토마타 만들기와 검색은 모두 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.