Kasai 알고리즘이 인접 접미사 LCP를 선형 시간에 계산할 수 있는 핵심 재사용은 무엇인가요?

Kasai의 핵심은 원문 시작 위치를 한 칸 옮길 때 앞서 확인한 공통 접두를 전부 버리지 않는 것입니다. rank[i]=r를 원문 suffix S[i..]의 suffix-array 순위라고 하고, r이 마지막 순위가 아니라면 SA[r+1]과의 LCP를 계산합니다. 직전 원문 위치에서 이 길이가 h였다면 시작점을 둘 다 한 칸 오른쪽으로 옮긴 두 suffix는 적어도 h-1글자를 공유합니다. 따라서 새 비교는 max(h-1,0)에서 시작하고, 그 뒤 처음 다른 글자까지 확장합니다.

예를 들어 어떤 원문 위치에서 다음 순위 suffix와 5글자를 공유했다면 다음 원문 위치의 비교 시작값은 4입니다. 새 글자들이 세 글자 더 같다면 현재 h는 7이 되지만, 이 증가분은 전체 순회에서 제한됩니다. 각 위치에서 h는 최대 한 번 줄고, 확장으로 늘어난 총량도 suffix 길이를 넘지 않으므로 문자 비교 합이 O(n)입니다. 매번 0에서 시작하면 반복 문자열에서 이미 확인한 접두를 계속 읽어 최악 O(n^2)으로 돌아갈 수 있습니다.

여기서는 LCP[r]=lcp(SA[r-1],SA[r])로 저장하는 이전 이웃 버전을 쓰겠습니다. 원문 위치 i의 rank가 r>0이면 j=SA[r-1]과 비교하여 LCP[r]에 h를 기록하고 다음 i를 위해 h를 최대 한 칸 줄입니다. r=0이면 이전 이웃이 없으므로 h=0으로 하고 건너뜁니다. banana의 SA는 [5,3,1,0,4,2]이고 ana(offset3)는 rank1, anana(offset1)는 rank2입니다. 따라서 LCP[2]=3입니다. 다음 이웃 버전도 가능하지만 그때는 저장 슬롯과 건너뛸 마지막 rank를 함께 바꿔야 합니다. 두 버전의 경계를 섞으면 오프바이원이 생깁니다.

실제 루프에서는 i를 증가시키기 전에 현재 h를 해당 rank의 LCP 슬롯에 기록하고, rank 0에서는 h=0으로 만든 뒤 다음 원문 위치로 넘어갑니다. banana처럼 ana와 anana가 반복되는 입력은 재사용을 눈으로 확인하기 좋고, 모든 문자가 같은 입력은 확장과 감소가 번갈아 일어나도 총합이 선형이라는 불변식을 시험합니다. SA와 rank를 서로 바꿔 쓰는 테스트는 결과가 그럴듯한 숫자를 내므로 offset과 rank를 각각 출력해 검증하는 편이 안전합니다.