접미사 배열을 구해 놓은 상태에서 인접한 것들을 비교하는 방법밖에 떠오르지 않는데 그렇게 하면 O(N^2)이라 필히 TLE입니다 ㅠㅠ

어떻게 하면 시간복잡도를 떨어뜨릴 수 있을까요?

접미사 배열을 이용해서 접미사 배열 내에서 모든 인접한 접미사끼리의 최장 공통 접두사의 길이를 O(N)에 계산하는 방법이 있습니다.

LCP라고 하는데, 참고자료는 여기로..

http://blog.naver.com/dark__nebula/220419358547

댓글을 작성하려면 로그인해야 합니다.