Dot Algo∙ DS/알고리즘 개념
2022. 4. 7.
[알고리즘] 접미사 배열(Suffix Array)와 LCP 배열(Lognest Common Prefix Array) (Java)
접미사(Suffix) 접미사(suffix)는 파생어를 만드는 접사로 단어 뒤에 붙어 새로운 단어가 되게 하는 말이다. 문자열 s의 i번째 접미사란, s 의 i번째 글자부터 마지막 글자까지 포함되는 부분문자열을 뜻한다. 문자열 "alohomora" A[i] S[A[i]···] 0 a l o h o m o r a 1 l o h o m o r a 2 o h o m o r a 3 h o m o r a 4 o m o r a 5 m o r a 6 o r a 7 r a 8 a 접미사 배열(Suffix Array) 문자열을 다룰 때 빼놓을 수 없는 자료 구조로 접미사 배열(Suffix Array)가 있다. 접미사 배열은 흔히 '문자열의 맥가이버 칼'이라고 불리며, 굉장히 다양한 문제를 푸는 데 쓸 수 있다. 접미사 배..
![[알고리즘] 접미사 배열(Suffix Array)와 LCP 배열(Lognest Common Prefix Array) (Java)](http://i1.daumcdn.net/thumb/C450x300/?fname=https://blog.kakaocdn.net/dn/cDx3aD/btryHapEg0x/Ppr1lZDsQfQw2FRfxqv6r0/img.png)