이해 구현 내가 Karkkainen, P. 샌더스에 의해 선형 시간 접미사 배열 생성 알고리즘의 구현을 이해하려고 노력하고 접미사 배열 선형 시간

Question

을 만들 수 있습니다. 알고리즘의 세부 사항은 here입니다.

나는 전체 개념을 이해하는 데 성공하지만, 제공하는 구현 및 명확하게 파악 따라서 수 없습니다와 일치하도록 실패. 여기

나를 혼동 초기 코드 경로입니다. 용지 당으로서

: 나 코드 당 3 내지 = (0,1,2)

를 개조에서 N0, N1, N2는 트리플렛의 개수가 시작 나타낸다 : N0 = (N + 2)/3, N1 =을 (n + 1)/3, n2 = n/3이고; 이 초기화는 어떻게 유도 되었습니까? ! 종이 당으로

: 우리는 i가 3 모드에서 세 쌍둥이의 연결입니다 T`를 작성해야 = 0 코드 당으로

: N02 =의 N0 + N2; s12 = [n02] ==> 어떻게 된거 야? n12, 즉 n1 + n2 여야합니다.

코드에 따라 : (int i = 0, j = 0, i < n + (n0 - n1); i ++) s12를 i % 3! = 0과 같은 세 쌍으로 채 웁니다. => for 루프가 n + (n0 - n1) 번 실행되는 이유는 무엇입니까? 그것은 단순히 n1 + n2이어야합니다. 그럴 수 없어?

나는 때문에 이러한 :(수 있도록 해주십시오 진행할 수 아니다

Answer 1

입력의 길이가 N = 13이고 다음 예제를 고려하십시오.

STA | CKO | WER | FLO | W 

코드 당으로 : = (N + 2)/3, 1 = (N + 1)/3, N2 = N/3 N0, 즉 => 이러한 initialisations 도출되었는지를

참고 난 mod3 트리플렛의 개수? = 0은 n mod3 = 0 인 경우 n/3이고 그렇지 않으면 n/3 + 1 (n mod3 = 1 또는 n mod3 = 2 인 경우). 현재 예제에서는 n/3 = 4이지만 마지막 삼중 항 'W'가 완료되지 않았으므로 정수 나누기에서 계산되지 않습니다. 이 계산을 직접 수행하는 '트릭'은 (n + 2)/3을 사용하는 것입니다. 사실, n mod3 = 0이면 정수 나누기 (n + 2)/3과 n/3의 결과는 같습니다. 그러나 n mod3 = 1 또는 2이면 (n + 2)/3의 결과는 n/3 + 1이됩니다. n1과 n2에도 동일하게 적용됩니다. 당 코드로서

: N02 = N0의 N2 +; s12 = [n02] ==> 어떻게 된거 야? n12, 즉 n1 + n2 여야합니다. 당 코드로서 ! 대 (INT I = 0, J = 0, I < N + (N0 - N1)는 I ++) 트리플렛과 S12을 작성되도록 I % 3 = 0; => for 루프가 n + (n0 - n1) 번 실행되는 이유는 무엇입니까? 그것은 단순히 n1 + n2이어야합니다. 그럴 수 없어?

두 질문

은 같은 대답이있다.

B12 = B1 U B2 = {TA KO ER LO} 

그래서 먼저 접미사를 정렬하고 8 개 요소를 가지고 B12의 접미사 배열로 끝날 것 : 우리의 예에서 우리는이 같은 B12 버퍼를 가질 것입니다. 머지 단계로 진행하기 위해 먼저 튜플 (B0 (i), rank (i + 1))을 정렬하여 얻은 B0의 접미사 배열을 계산해야합니다.분류

B0 = {0,3,6,9,12} 

가 알파벳 순으로

결과 : 순위 (I + 1) B0의 마지막 요소에 대해 정의되어 있지 않기 때문에 그러나 마지막 삼중는 하나 개의 요소 (W)을 가지고있는이 콘크리트의 경우는 문제가 인덱스 6, 12 이후

SA0 = {3, 9, 0, ?, ?} 

, 오 .. 우리가 처음 순위 테이블에 이동하는 확인해야하는 'W'가,이 알파벳 순으로 정렬하는 것만으로는 충분하지 않습니다 포함, 그래서 자신의 접미사의 순위를 확인하자 기다림! rank (13)가 정의되지 않았습니다!

마지막 삼중 항에 하나의 요소 만 포함되어있는 경우 입력의 마지막 삼중 항에 더미 0을 추가하는 이유가 여기에 있습니다 (n mod3 = 0 인 경우). 따라서 B12의 크기는 n1의 크기와 관계없이 n0 + n2이며, B0이 B1보다 큰 경우 B12에 추가 요소를 추가해야합니다 (이 경우 n0-n1 = 1).

희망적입니다.