O (n logn)에서 접미사 배열

Question

codechef 및 stackoverflow에서도 접미사 배열 구성 자습서를 읽고 있습니다. 내가 이해할 수있는 한 가지 점은 그들이 말하는 것입니다.

원래 문자열 S의 2-grams (*), 4-grams, 8-grams 등을 먼저 정렬하고, 그래서 i-th 반복에서 우리는 2i 그램을 정렬합니다.

등등. 반복 할 때마다 나는 두 단계가 있습니다

2 단계 비교 (즉 O (1) 시간) 각

만들기 새로운 사전 식 이름을 사용하려면 이전 반복에서 사전 식 이름을 사용하여, 2I 그램에 의해 정렬을

MY DOUBT IS : 4-gram을 위해 2-gram으로 계산 된 인덱스를 어떻게 사용할 수 있습니까? ?

제 2 접미사가 'ab', 'ac'라고 가정하고 O (1) 시간을 비교하여 색인을 제공 할 수있는 방법은 무엇입니까?

나는 정말로 시도했지만 거기에 머물렀다. 도움이되는 몇 가지 예를 제공해주십시오. ks를 미리 입력하십시오.

Answer 1

길이가 2^k 인 모든 부분 문자열이 정렬되어 이제는 길이가 2^(k + 1) 인 모든 하위 문자열을 정렬한다고 가정합시다. 여기에서 중요한 관찰은 길이가 2^(k + 1) 인 서브 스트링이 길이가 2^k 인 두 개의 서브 스트링의 연결이라는 것입니다.
예를 들어, 문자열 abacaba에서 하위 문자열 caba은 ca과 ba의 연결입니다.
그러나 길이가 2^k 인 모든 하위 문자열이 정렬되므로이 길이가있는 모든 하위 문자열의 정렬 된 배열에있는 위치를 기준으로 각각에 [0 ... n - 1] 범위의 정수가 할당되어 있다고 가정 할 수 있습니다 (동일한 문자열 동일한 수를 할당해야하며이 배열은 명시 적으로 유지 관리되지 않습니다. 이 경우, 길이가 2^(k + 1) 인 각 부분 문자열은 두 개의 숫자 쌍 (각각 첫 번째와 두 번째 부분 문자열의 클래스)으로 나타낼 수 있습니다. 따라서 우리가해야 할 일은 범위가 [0 ... n - 1] 인 정수 쌍의 배열을 정렬하는 것입니다. 하나의 기수 정렬을 사용하여 선형 시간으로 수행 할 수 있습니다. 이러한 쌍을 정렬 한 후 정렬 된 배열에서 단일 패스를 사용하여 길이가 2^(k + 1) 인 모든 하위 문자열에 대한 클래스를 찾을 수 있습니다.