문자열 검색 효율을 높이는 최적의 자료구조는 무엇인가?

접두사로 찾거나 자동완성을 붙일 때는 트라이(Trie)다. 문자열 검색이라고 늘 트라이는 아니다. 문자열을 트리 구조로 저장해 접두사 공유로 탐색 시간을 문자열 길이에 비례하게 줄인다.

트라이는 문자열의 공통 접두사를 노드로 공유한다. 동일한 시작 문자를 가진 단어들은 같은 경로를 따라가므로 중복 탐색을 피한다.

KMP나 라빈-카프 알고리즘은 특정 텍스트 내에서 패턴을 찾을 때 쓴다. 트라이는 사전(Dictionary)처럼 여러 단어를 빠르게 검색하거나 자동완성에 적합하다.

시간 복잡도는 O(L)이다. 여기서 L은 검색하려는 문자열의 길이이며, 데이터셋의 크기와 상관없이 일정하게 유지된다.