K 최대 서브 문자열 찾기

Question

길이가 10^5 인 S을 제공하고 있습니다. 가능한 모든 문자에 대해 N+1C2 부분 문자열은 모든 부분 문자열이 오름차순으로 정렬 될 때 K 부분 문자열을 출력해야합니다.

For Ex: 
S= STACK 

Substring: 
    A 
    AC 
    ACK 
    C 
    CK 
    S 
    ST 
    STA ... so on 

My Approach : 모든 하위 문자열이 K 하위 문자열 다음

은 내가 접미사 배열을 생성 한 특정 문자열에 대한 Suffix 배열을 알고 듯했으나, K을 계산하는 방법을 그들과 출력을 분류 생성 접미사 배열을 사용하는 요소? Suffix Array을 사용하여 K 요소를 계산하는 방법을 설명해 주시겠습니까?

접미사 배열을 생성하고 이해 했습니까? 그러나 그것을 사용하는 방법.

Answer 1

접미사 트리는 문자열의 모든 접미사를 제공합니다. 따라서 문자열이 "스택"인 경우 가장 긴 접미어는 $ 스택입니다 (접미사가 다른 접미사의 접두어가되지 않도록 추가 문자를 추가합니다). 그 다음으로 긴 것은 tack $이고, 그 다음엔 $입니다. 이 모든 것은 루트에서 액세스 할 수 있습니다.

이제 하위 문자열은 접미사의 접두사 일뿐입니다. 나무를 걷는 것만으로 모든 하위 문자열을 정렬 할 수 있습니다. 그것은 하나의 값 비싼 솔루션입니다. 검색을 더 저렴하게하려면 K = 5라고 말하십시오. 접미사는 A로 시작하고 끝 기호 $까지 세 경로가 있습니다. 그래서 A는 접미사의 시작이 아닙니다. 접미사 B가 시작되지 않습니다. 그래서 우리의 대답이 아닙니다. 우리는 접미사가 C로 시작하고 $에 두 개의 경로가 있습니다. 따라서 k = 5 인 경우 접미사의 첫 글자는 'C'여야합니다. 그런 다음 확장합니다. 우리는 a에 3 개의 위치를 ​​잃었으므로 첫 번째 C 노드 아래에 두 번째 접미사가 필요합니다.