인가-K-하위 문자열 접미사 트리

Question

내가 정점의 수는 O에 의해 제한되어있어 문자열 s의 접미사 트리와 함께, 다음 작업을 할 수있는 방법과 기능 (| S |) :

인가-K -Sub-string (r) - 문자열 r이 s의 k-sub-string인지 확인합니다. 여기서 k-sub-string은 다음과 같이 정의됩니다.

s의 하위 문자열 r이 k- 서브 문자열에 대한 s의 파티션이있는 경우 문자열 :

r = x1x2 ... xk; xi = s의 부분 문자열.

예 : s = whitething, r = within, r은 s의 3-sub-string입니다.

O (| r |)의 복잡성에서 작동하려면이 연산이 필요합니다.

r에있는 각 문자가 2-Sub-string과 같이 현재 구분 기호 일 수 있으므로 O (| r |)에서 어떻게 수행하는지 이해할 수 없으므로 모든 문자를 시도해야합니다. 가능한 문자를 x1과 x2 (파티션 r = x1x2) 사이의 구분 기호로 사용하십시오.

아이디어가 있으십니까?

Answer 1

보조 정리는 : A는 B 및 B의 접미사 인 경우 S 중 가장 k 문자열로 분할, 그래서 A 할 수 할 수 있습니다.

증명 : let B = x[1] x[2] x[3] ... x[k]. 파티션의 첫번째 문자 인 |B| - |A|을 버리자. 우리는 k 부분 이상의 파티션을 얻습니다.

결과 : R이라는 고정 접두어가있는 고정 파티션이있는 경우 다음 하위 문자열이 가장 길어질 수있는 최적의 파티션이 있습니다.

위의 입증 된 내용은 바로 다음과 같습니다. 우리는 우리가 할 수있는 각 부분을 만들 수 있습니다

pos = 0 
while pos < R.length: 
     take the longest prefix of R[pos:] that is a substring of R 
     move pos after the end of this substring 

이 솔루션은 선형 시간에서 구현 될 수있다 : 우리가 나무의 뿌리에서 시작하고 길이의 현재 문자의 전환을 자신의 계속 할 수 있습니다 R. 없는 경우, 현재 파트를 응답에 추가하고 루트에서 다시 시작합니다.