문자열 알고리즘 — KMP, Rabin-Karp, 접미사 배열

문자열 알고리즘은 프로그래밍에서 가장 실용적인 분야 중 하나예요.

여러분이 구글에서 검색할 때, 수십억 개의 웹페이지에서 원하는 단어를 찾아야 해요.

생물정보학에서는 30억 개의 DNA 염기쌍에서 특정 유전자 서열을 찾아야 하고요.

에디터에서 Ctrl+F를 누르면 실시간으로 모든 {매칭→매칭}을 하이라이팅해줘야 해요.

왼쪽 네 개의 상자를 보세요. 검색 엔진, 생물정보학, 에디터, 보안 분야에서 모두 핵심이에요.

가장 단순한 방법인 브루트 포스는 텍스트의 모든 위치에서 {패턴→패턴}을 비교하는 거예요.

아래쪽 빨간 막대를 보시면, O(nm)이에요. n은 텍스트 길이, m은 {패턴→패턴} 길이죠.

텍스트가 10억 글자이고 {패턴→패턴}이 100만 글자면, 10의 15승 번 비교해야 해요.

이건 슈퍼컴퓨터로도 현실적이지 않은 시간이에요.

그래서 똑똑한 알고리즘이 필요한 거예요. {KMP→케이엠피} 알고리즘은 이미 비교한 정보를 재활용해요.

{Rabin-Karp→라빈카프}는 {hash→해시} 함수를 써서 문자열을 숫자로 변환하고 비교해요.

파란색과 녹색 막대를 보세요. 둘 다 O(n+m)에 해결할 수 있어요.

브루트 포스보다 백만 배 빠른 거죠! 오른쪽 화살표가 그 차이를 보여줘요.

오른쪽 점선 상자에 이 레슨의 학습 로드맵이 있어요.

{접미사 배열→서픽스 어레이}은 텍스트의 모든 접미사를 정렬해서 이진 탐색으로 {패턴→패턴}을 찾아요.

Z 알고리즘, 문자열 {해싱→해싱}, {Aho-Corasick→아호코라식} 같은 고급 기법도 배울 거예요.

이 레슨에서는 실제 코드와 함께 각 알고리즘의 핵심 아이디어를 체험해볼 거예요.

특히 "왜 이 알고리즘이 빠른가"를 직관적으로 이해하는 게 목표예요.

하단의 결론 문장을 보세요. 핵심은 이미 비교한 정보를 재활용하는 거예요.

먼저 브루트 포스의 한계를 정확히 이해하고, 거기서 {KMP→케이엠피}가 어떻게 개선되는지 볼게요.

그 다음 {해시→해시} 기반 접근법, {Trie→트라이}, {접미사 배열→서픽스 어레이} 순서로 진행할 거예요.

각 알고리즘마다 실제 문자열로 직접 손으로 따라가볼 거예요.

자, 그러면 브루트 포스부터 시작해볼까요?