3033번 - 가장 긴 문자열
안녕하세요~
string matching에 관해서 공부하던 중 궁금한 점이 있어 질문드립니다
3033번 문제의 경우, max input 크기가 2*10^5입니다.
suffix array를 생성하는 데에는 O(n*log^2n) 만큼의 시간이 걸리므로 시간복잡도의 문제가 없으나,
i, i+1 쌍에 대해서 LCP를 확인하는 데에는 worst case input(aaaaa..... * 10^5)의 경우 ~O(n^2/2) = O(n^2)가 걸립니다.
물론 일반적인 문자열들에 대해서 이보다 훨씬 낮은 시간복잡도를 가질거라 추측되지만 (~O(n)),
worst case를 제외한 평균적인 경우에 대해서 suffix array가 충분한 성능을 보장한다는 이론적 근거가 있을까요?
친절한 답변 미리 감사드립니다!
LCP도 O(n)에 계산이 가능합니다
댓글을 작성하려면 로그인해야 합니다.
jth 6년 전
안녕하세요~
string matching에 관해서 공부하던 중 궁금한 점이 있어 질문드립니다
3033번 문제의 경우, max input 크기가 2*10^5입니다.
suffix array를 생성하는 데에는 O(n*log^2n) 만큼의 시간이 걸리므로 시간복잡도의 문제가 없으나,
i, i+1 쌍에 대해서 LCP를 확인하는 데에는 worst case input(aaaaa..... * 10^5)의 경우 ~O(n^2/2) = O(n^2)가 걸립니다.
물론 일반적인 문자열들에 대해서 이보다 훨씬 낮은 시간복잡도를 가질거라 추측되지만 (~O(n)),
worst case를 제외한 평균적인 경우에 대해서 suffix array가 충분한 성능을 보장한다는 이론적 근거가 있을까요?
친절한 답변 미리 감사드립니다!