79brue의 PS 블로그

scpc를 대비하기 위해 문자열 알고리즘을 공부해 보기로 했다. 대표적인 문자열 알고리즘으로는 KMP, 라빈 카프 (해싱), 트라이 등이 있다. Z와 Manacher는 그에 비해서는 조금 덜 유명한 알고리즘이지만, 알아 두는 것이 좋을 것 같아 공부해 두기로 했다. 다음 글들을 참고하였다.Zhttps://cp-algorithms.com/string/z-function.htmlhttps://gina65.tistory.com/29Manacherhttps://ialy1595.github.io/post/manacher/ Z 알고리즘Z 알고리즘이 구하고자 하는 것은 Z array이다. 어떤 길이 $n$인 문자열 $S$의 Z array는 $S$와 $S[i:]$ (모든 접미사)의 최장 공통 접두사 길이로 정의된다. ..