접미사 배열·LCP 계산기

문자열의 모든 접미사를 사전순으로 늘어놓고 그 시작 위치만 적어 둔 배열입니다. banana라면 a(5), ana(3), anana(1), banana(0), na(4), nana(2) 순이므로 접미사 배열은 [5, 3, 1, 0, 4, 2]가 됩니다. 접미사 자체를 저장하지 않고 위치만 담으므로 메모리는 문자열 길이에 비례합니다.

어떤 부분문자열이든 이분 탐색으로 O(m log n)에 찾습니다. 찾는 문자열로 시작하는 접미사들은 사전순으로 늘어놓으면 반드시 붙어 있으므로, 그 구간의 양 끝만 찾으면 몇 번 나오는지와 어디에 있는지가 한꺼번에 나옵니다. 텍스트를 한 번 만들어 두고 패턴을 여러 개 찾을 때 특히 유리합니다.

서로 다른 부분문자열의 개수를 n(n+1)/2 − ΣLCP로 즉시 세기 위해서입니다. 전체 부분문자열 n(n+1)/2개에서, 사전순으로 앞선 접미사와 앞부분이 겹쳐 이미 세어진 만큼을 빼는 셈입니다. LCP의 최댓값은 두 번 이상 나오는 가장 긴 조각의 길이이기도 합니다.

긴 접미사부터, 즉 위치 0, 1, 2… 순서로 보기 때문입니다. 위치 i의 LCP가 h라면 위치 i+1의 LCP는 최소 h−1입니다. 앞 글자 하나만 떼어 낸 접미사라 공통 부분도 한 글자만 줄어들 뿐이기 때문입니다. 그래서 h를 0으로 되돌리지 않고 이어서 세면 전체 비교 횟수가 2n을 넘지 않습니다.

패턴 쪽을 미리 손질하느냐, 텍스트 쪽을 미리 손질하느냐가 다릅니다. KMP와 라빈–카프는 패턴마다 준비를 하고 텍스트를 한 번 훑어 O(n + m)에 찾습니다. 접미사 배열은 텍스트를 한 번 준비해 두고 패턴을 O(m log n)에 찾으므로, 같은 텍스트에서 패턴을 여러 번 찾을수록 유리해집니다.

됩니다. 자바스크립트 문자열은 UTF-16이라 이모지 하나가 두 칸을 차지하는데, 그대로 자르면 접미사가 반쪽에서 시작해 사전순이 뒤틀립니다. 이 도구는 코드포인트 단위로 쪼갠 뒤 다루므로 이모지가 섞여도 접미사 경계가 깨지지 않습니다.

전송되지 않습니다. 접미사 정렬과 검색은 모두 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.