suffix array와 LCP 합으로 서로 다른 부분 문자열 수를 계산할 때 중복을 어떻게 빼나요?

길이 n인 문자열의 위치가 구별되는 부분 문자열 후보는 각 시작점의 접두 길이를 합친 n(n+1)/2개입니다. 하지만 문자열 내용이 같은 후보는 하나로 세야 합니다. suffix array 순서에서 현재 suffix가 새로 보태는 것은 자신의 길이 n-SA[r] 중, 바로 앞 suffix와 공유하는 LCP[r]개의 짧은 접두를 제외한 부분입니다. 즉 새 기여는 n-SA[r]-LCP[r]이고, 이를 모두 더하면 n(n+1)/2 - ΣLCP[r]가 됩니다. 여기서 “LCP를 누적한다”는 것은 전역 합을 말하며, 각 suffix의 중복 길이를 여러 이전 suffix와의 LCP 합으로 해석하면 안 됩니다.

aba에서는 suffix 길이가 3, 2, 1이므로 후보가 6개입니다. 사전순 suffix는 a, aba, ba이고 LCP는 1, 0입니다. 첫 suffix는 a를 새로 내고, 두 번째는 앞의 a를 제외한 ab, aba 두 개를 내며, 세 번째는 b, ba 두 개를 냅니다. 따라서 1+2+2=5, 공식도 6-(1+0)=5입니다. LCP 하나가 문자열 전체의 중복 개수라는 뜻이 아니라, 해당 suffix가 앞선 정렬 영역에 이미 기여한 접두의 경계를 나타낸다는 점이 중요합니다.

실제 구현은 빈 문자열이면 0, 한 글자면 1로 처리하고, sentinel을 내부 정렬용으로 넣었다면 그 sentinel suffix와 관련 LCP를 계산 대상에서 제외합니다. SA 구성은 보통 O(n log n), Kasai는 O(n), LCP 합산은 O(n)이므로 질의보다 전처리 비용이 먼저입니다. 이 공식은 해시 충돌 확률에 기대지 않지만, SA와 LCP가 같은 문자 단위와 끝 규칙으로 만들어졌다는 전제가 필요합니다.

이 계산은 “바로 앞 suffix만 보면 충분한가”라는 의문이 생기는데, suffix array의 사전순 prefix들은 연속되어 있으므로 현재 suffix가 이전 어느 suffix와 공유하는 최대 prefix 길이가 바로 직전 suffix와의 LCP로 대표됩니다. 그래서 각 행의 새 기여를 더할 때 중복을 여러 번 빼지 않습니다. aaaa도 좋은 경계 사례입니다. 정렬 순서 a,aa,aaa,aaaa의 인접 LCP는 1,2,3입니다. 전체 후보 10개에서 합 6을 빼면 실제 distinct 값은 a,aa,aaa,aaaa의 4개입니다. 이는 suffix 길이 합을 올바르게 계산해야 한다는 확인 포인트입니다.