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가 충분한 성능을 보장한다는 이론적 근거가 있을까요? 

친절한 답변 미리 감사드립니다!

ho94949   6년 전

LCP도 O(n)에 계산이 가능합니다

jth   6년 전

아 그렇네요! 감사합니다~ 

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