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의 정의에 의해 두 번 이상 나오는 문자열 중 가장 긴 문자열은 lcp배열에서 최댓값이기 때문이다.
이 문제의 응용이 다른데서 lcp의 대표문제라고 언급되는 BOJ_공통 부분 문자열 이다. 두 문자열에서 최장 공통 부분 문자열의 크기와 그것을 구하는 문제인데, 두 문자열을 이어준 후( 반드시 두 문자열 사이에 dummy 문자 하나를 넣어 주어야한다. 그냥 이을경우 abcd + bacdba 경우에... 처참하다) lcp의 최대값을 구해주면 답이 나온다.
물론 이 때 인접한 두 suffix가 서로 다른 문자열에 있을 경우에만 lcp의 len을 ++시켜주어야한다.
