문자열 검색 최적화 시 어떤 기준으로 알고리즘을 고르는가?

검색 대상의 크기, 패턴의 반복성, 그리고 검색 빈도에 따라 고른다. 정적인 사전에서 빠른 조회가 필요하면 트라이를, 긴 텍스트 내 단일 패턴 검색은 KMP나 라빈-카프를 쓴다.

트라이는 문자열을 트리 형태로 저장해 접두사 공유를 극대화한다. 한 번 구축하면 검색 시간이 문자열 길이에 비례한다. 대신 각 노드의 포인터 배열이 메모리를 많이 쓴다.

KMP는 패턴 내부의 반복 구조를 미리 계산해 불필요한 비교를 건너뛴다. 텍스트를 되돌아가지 않아 각 글자를 거듭 비교하지 않는다.

라빈-카프는 해시 값을 이용해 문자열을 비교한다. 해시가 일치할 때만 실제 문자열을 대조하므로, 여러 패턴을 동시에 찾거나 대용량 데이터를 처리할 때 유리하다.