11479번 - 서로 다른 부분 문자열의 개수 2
접미사 배열을 구해 놓은 상태에서 인접한 것들을 비교하는 방법밖에 떠오르지 않는데 그렇게 하면 O(N^2)이라 필히 TLE입니다 ㅠㅠ
어떻게 하면 시간복잡도를 떨어뜨릴 수 있을까요?
접미사 배열을 이용해서 접미사 배열 내에서 모든 인접한 접미사끼리의 최장 공통 접두사의 길이를 O(N)에 계산하는 방법이 있습니다.
LCP라고 하는데, 참고자료는 여기로..
http://blog.naver.com/dark__nebula/220419358547
댓글을 작성하려면 로그인해야 합니다.
medic_programmer 7년 전
접미사 배열을 구해 놓은 상태에서 인접한 것들을 비교하는 방법밖에 떠오르지 않는데 그렇게 하면 O(N^2)이라 필히 TLE입니다 ㅠㅠ
어떻게 하면 시간복잡도를 떨어뜨릴 수 있을까요?