접미어 배열과 LCP 배열을 사용하여 문자열의 i 번째 하위 문자열을 찾는 방법은 무엇입니까?

Question

우리가 사 전적으로 문자열의 모든 별개의 하위 문자열을 배열하고 우리는 그것이 suffix array 및 LCP array의 사용을 찾을 수 있나요 문자열

1) i 번째 필요하면?

2.) 그렇다면 어떻게해야합니까? 이것은 N (O의 시간 복잡도를 갖는다 Manber & 마이어스 (Nlog^2N)을 사용하여 접미사 배열을 만드는 동안 O (Nlog^N)에서 수행하거나 생성하는 동안 그 O의 시간 복잡도를 갖는다 카사이의 알고리즘을 사용하여 LCP 어레이의 수)?

Answer 1

예 접미어 배열과 LCP 배열을 사용하여 수행 할 수 있습니다.

접미어 배열 및 LCP 배열을 계산하는 방법을 알고 있다고 가정합니다.

접미사 배열 lcp[]을 나타내는 p[]은 LCP 배열을 나타냅니다.

는 i'th 순위 접미사까지 별개의 서브 스트링들의 수를 저장 배열을 만든다. 이 수식을 사용하여 계산할 수 있습니다. 단지 누적 배열 cum[]에 i의 하한을 찾을 i'th 하위 문자열을 찾기 위해 지금

cum[0] = n - p[0]; 
for i = 1 to n do: 
    cum[i] = cum[i-1] + (n - p[i] - lcp[i]) 

를 : 자세한 내용은 Here

이 cum[]은 다음과 같이 계산 될 수 누적 배열을 표시하자 참조하십시오 그러면 하위 문자열을 시작하여 모든 문자를 길이까지 인쇄 할 위치에서 접미사의 순위를 알 수 있습니다.

i - cum[pos-1] + lcp[pos] // i lies between cum[pos-1] and cum[pos] so for finding 
          // length of sub string starting from cum[pos-1] we should 
          // subtract cum[pos-1] from i and add lcp[pos] as it is 
          // common string between current rank suffix and 
          // previous rank suffix. 

여기서 pos은 하한값으로 반환 값입니다.

전체 위의 과정은 다음과 같이 요약 될 수있다 : LCP와 논리 위에 당신이