🔤문자열
Strings Algorithms
Pattern matching sliding over text. Learn the 3 topics below step by step with interactive visualizations.
🔤KMP 문자열 탐색 (Knuth-Morris-Pratt)
실패 함수(LPS)를 미리 계산해, 불일치가 나도 패턴을 처음부터 다시 비교하지 않고 건너뛰는 문자열 탐색입니다. 텍스트 포인터를 되돌리지 않아 O(n+m)에 매칭합니다.
O(n + m)🔤라빈-카프 (Rabin-Karp)
패턴과 텍스트 구간의 해시값을 비교하는 문자열 탐색입니다. 롤링 해시로 구간 해시를 O(1)에 갱신하며, 해시가 같을 때만 실제 문자를 확인해 다중 패턴 검색에 유리합니다.
평균 O(n + m)🔤보이어-무어 (Boyer-Moore)
패턴을 오른쪽 끝부터 비교하고, 불일치 시 나쁜 문자 규칙으로 패턴을 크게 점프시키는 탐색입니다. 텍스트의 많은 글자를 건너뛸 수 있어 실무에서 가장 빠른 단일 패턴 탐색 중 하나입니다.
최선 O(n / m)