LCP : longest common prefix로
두 문자열의 최장 공통 접미사를 찾는 것이다
이 문제를 풀 때는 가장 많이 사용하는 방법이 Suffix array이다
suffix array를 사용하기 전 시간 복잡도는 O(N)이고
사용한 후는 O(Nlog(N)) 이다
이후 suffix array를 사용 후 LCP 탐색을 하면
시간 복잡도는 O(N*(logN)**2) 이다
접미사 배열을 사용한 후 LCP 탐색을 하게 되면 얻는 이점은
첫 글자가 다르다는 것을 확인하게 되면 그와 관련된 그룹은 전부 pass 할 수 있다는 것이다
예를 들면 mississipi 에서 접미사 ipi와 issipi가 포함된 그룹이 있고 si가 있다
이 둘을 비교할때 첫글자인 i와 s가 다르기 때문에 전부 건너뛰어 시간을 절약할 수 있다.
https://shin8037.tistory.com/