TOC
문자열 알고리즘
다항식 롤링 해시
- 부분문자열이 등장하는 지를 빠르게 확인할 수 있다.
- 라빈-카프 알고리즘에 사용된다.
접두사 배열
Z-알고리즘
와 의 최장 공통 접두사 - 위의 Z-배열Z-array을 구하는 알고리즘
- 패턴 매칭과 반복되는 부분 문자열을 찾는 데에 사용될 수 있다.
트라이 (접두사 트리)
- 빠른 접두사 검색에 사용할 수 있다.
아호-코라식 알고리즘
- 일대다(haystack은 한 개, needle은 여러 개) 패턴 매칭을 위해 트라이를 개선한 것이다.
매나커 알고리즘
- 최장 팰린드롬 부분 문자열을
에 찾을 수 있는 알고리즘이다.