hellogaon

접미사 배열(Suffix Array)은 어떤 문자열의 모든 접미사를 사전순으로 정렬해 둔 배열입니다.이를 구하기 위해 문자열의 접미사들을 모아놓은 뒤 정렬을 하게 되면길이가 N인 문자열의 접미사의 개수는 N개 이므로 O(NlgN)번 비교연산을 진행하지만string은 한 번 비교연산을 할 때마다 틀릴 때까지 앞글자부터 하나하나 비교를 하기에 시간복잡도가 O(N^2 lgN)입니다.이 때 좀 더 빠르게 접미사 배열을 만들기 위하여 맨버-마이어스 알고리즘을 사용합니다.접미사들의 특성을 이용하여 매번 접미사를 첫 한글자, 두글자, 네글자, 여덟글자... 기준으로 정렬하며매번 이전 정렬에서 얻은 정보를 이용하여 두 문자열을 빠르게 대소 비교합니다.이러한 과정으로 진행하면 비교연산을 O(lgN)번으로 줄일 수 있으며..