알고리즘/잡설
suffix array + lcp
1. suffix array설명은 갓-crocus 블로그가, lcp설명은 plzrun 블로그가 제일 정리가 잘 되어있다. 2. suffix array의 존재이유는 lcp를 위해 있다고 해도 과언이 아니다. 3. O($nlogn$)만에 구하는 알고리즘도 있다. O($nlog^2n$) 알고리즘보고 오 기수정렬이랑 비슷하다 생각했는데 역시 radix sort를 이용한단다. 자료구조수업때 한번 본 이후로 처음 보며 처음 써본다. 제대로 이해하기 위해서는 radix sort를 다시 봐야겠다. 설명은 plzrun 블로그. 4. lcp가 이용되는 대표적인 문제는 BOJ_가장 긴 문자열 이다. 한 문자열에서 두 번 이상 나오는 문자열을 포함하는 suffix는 suffix array에서 항상 인접하고, lcp의 정의에 ..
