PS 문자열 알고리즘 - 0. Introduction

 

PS를 하다보면 몇몇 문자열 알고리즘을 마주할 수 있다. KMP, 해싱, 라빈 카프, 아호 코라식, 매내처 등 다양한 알고리즘들이 있다. 이들 대부분 플래티넘 난이도에 기본 문제가 속할 정도로 꽤나 난이도가 있는 알고리즘들이기에 이를 한 번 정리할 필요성이 있다고 느꼈다. 그리고 무엇보다도 필자의 #string 레이팅이 아래 그림과 같이 미세하지만 오목한 것을 발견해 이를 볼록 다각형으로 바꿔놓기 위해서 문자열 알고리즘을 공부할 필요가 있다고 느꼈기 때문이기도 하다.

convex polygon을 만들어야 한다는 집념

 

 

그래서 순차적으로 문자열 알고리즘을 올려 보려고 한다.

 

아래는 매 게시글을 올릴 때마다 추가할 목차이다.

 

[1] KMP 알고리즘의 원리&구현: https://kdy40929.tistory.com/3

PS 문자열 알고리즘 - 1. KMP 알고리즘

[2] KMP 알고리즘 응용: https://kdy40929.tistory.com/5

PS 문자열 알고리즘 - 2. KMP 응용

[3] Z 알고리즘: https://kdy40929.tistory.com/6

PS 문자열 알고리즘 - 3. Z 알고리즘

[4] 매내처 알고리즘: https://kdy40929.tistory.com/7

PS 문자열 알고리즘 - 4. Manacher 알고리즘

[5] 해싱 (라빈 카프): https://kdy40929.tistory.com/8

PS 문자열 알고리즘 - 5. 라빈 카프 알고리즘 (해싱)

[6] 접미사 배열과 lcp 배열 원리/구현: https://kdy40929.tistory.com/9

PS 문자열 알고리즘 - 6. 접미사 배열과 lcp 배열

[7] 접미사 배열과 lcp 배열 활용: https://kdy40929.tistory.com/10

PS 문자열 알고리즘 - 7. 접미사 배열과 lcp 배열 응용

[8] 1D Trie: https://kdy40929.tistory.com/11

PS 문자열 알고리즘 - 8. 1D Trie 구현

[9] 아호 코라식: 추후 작성 예정