아호에이투(Aho-Corasick Algorithm)는 문자열 검색을 위한 알고리즘으로, 다수의 패턴을 동시에 찾는 데 효율적이다. 이 알고리즘은 1975년 알프레드 아호(Alfred V. Aho)와 마이클 코라식(Michael J. Corasick)에 의해 제안되었다.

아호에이투는 주로 두 가지 단계로 구성된다. 첫 번째 단계는 여러 개의 검색할 문자열(패턴)을 포함하는 트라이(Trie) 구조를 구축하는 것이다. 이 트라이는 각 패턴의 문자들이 노드로 표현되어, 문자열 검색 시 신속하게 패턴을 탐색할 수 있도록 돕는다. 트라이를 구축한 후, 각 노드에 대해 실패 링크(failure link)를 설정하여 검색 시 불일치가 발생했을 때 빠르게 되돌아갈 수 있도록 만든다.

두 번째 단계에서는 텍스트를 순차적으로 스캔하면서 트라이를 탐색하고, 특정 문자에서 패턴의 마지막 노드에 도달하면 해당 패턴의 발견을 기록한다. 이 과정에서 실패 링크를 사용하여 불일치가 발생한 경우 빠르게 다른 경로로 이동할 수 있어, 전체 텍스트를 선형 시간 복잡도 O(n + m + z)로 처리할 수 있다. 여기서 n은 텍스트의 길이, m은 패턴의 총 길이, z는 발견된 패턴의 수를 나타낸다.

아호에이투 알고리즘은 바이러스 백신 소프트웨어, 데이터베이스 검색, 자연어 처리 및 DNA 서열 분석 등 다양한 분야에서 활용되며, 다수의 패턴을 효율적으로 검색할 수 있는 장점을 제공한다.