시프트 문자열의 데이터 구조

Question

우리는 이진 문자열에 대한 데이터 구조에 관심이 있습니다. S = s로하자. .... s _m은 크기가 m 인 이진 문자열이어야한다. Shift(S,i)은 문자열의 순환 시프트 Si 왼쪽 공백입니다. 즉, (S, I) = 시프트이다 s의 I _{S I + S 1 + I 2} ... S _미터 S ₁ ... I-1의_{. 지원하는 효율적인 데이터 구조를 제안한다 : (1)}

Insert(s)가 O의 DS에 이진 문자열을 삽입 O에서 empy DS의

1. Init()을
2. Search_cyclic(s) 확인되는 경우 (|^2 | S) O (| s |)에 ANY i에 대해 Shift(S,i)이 있습니다.

공간 복잡도 : O (| S ₁ | + | S ₂ | + ..... + | S _m |) S _I는 m 스트링 경우이다 어디 이것까지 삽입했습니다.

일부 주어진 i에 대해 Search_cyclic (s, i)를 찾아야하는 경우 접미사 트리를 사용하고 O (| s |)로 건너 뛴다는 것이 매우 간단합니다. 그러나 Search_cyclic (s)에는 주어진 i가 없으므로 주어진 복잡성에서 무엇을해야할지 모르겠습니다. OTOH, Insert (s)는 일반적으로 접미어 트리에 삽입하기 위해 O (| s |)를 취하고 여기서 O (| s |^2)를 부여받습니다.

Answer 1

그래서 여기 제가 제안 할 수있는 해결책이 있습니다. 복잡성은 당신이 물어 본 것보다 더 낮지 만 조금 복잡해 보일 수 있습니다.

모든 문자열을 유지하는 데이터 구조는 Trie 또는 심지어 Patricia tree이됩니다. 각 문자열에 대한이 트리에서 가능한 모든 시프트 중에서 최소주기 시프트 (즉, 사전식이 최소 인 모든 가능한 시프트의 순환 시프트)를 삽입하려고합니다. 선형 시간에 문자열의 최소 순환 시프트를 계산할 수 있습니다. 나중에 그 비트에 가능한 해결책을 하나씩 제공 할 것입니다. 잠시 동안 당신이 그것을 할 수 있다고 가정하십시오. 여기에 필요한 작업을 구현하는 방법입니다 :

1. 초기화() - 모두 트라이 패트리샤 트리의 init을 일정 - 여기에 문제
2. 삽입 (들) - 당신이 계산 최소 순환 쉬프트의 '의 O (| s |)의 데이터 구조에 삽입 한 다음 O (| s '|) = O (| s |)의 데이터 구조 중 하나에 삽입하십시오. 이것은 요구되는 복잡성보다 훨씬 우수합니다.
3. Search_cyclic - 다시 O (| s |)에서 s의 최소 순환 시프트를 계산 한 다음 문자열이 존재하면 Patricia 또는 Trie를 체크인합니다.

또한 Patricia를 구성하는 경우 메모리 복잡성이 필요하며 더 낮을 수도 있습니다.

그래서 남은 것은 최소한의 순환 시프트를 찾는 방법을 설명하는 것입니다. 접미어 트리에 대해 언급 한 이후로 나는 linear time에 그것을 구성하는 방법을 알기를 바랍니다. 트릭은 - 문자열 s를 자신에게 추가합니다 (예 :두 배로 만든 다음 두 줄로 된 접미어 트리를 만듭니다. 이것은 | s |와 관련하여 여전히 선형 적입니다. 그래서 아무런 문제도 없습니다. 그 후에해야 할 일은이 트리에서 길이 n의 접미사를 찾는 것입니다. 이것은 내가 믿기에는 어렵지 않다. 루트에서 시작하여 길이가 길어질 때까지 최소한의 문자열이있는 현재 노드의 링크를 항상 따라 가야한다. 문자열을 두 배로 늘리므로 적어도 | s | 길이를 누적 할 때까지 최소한의 문자열 링크를 따라갈 수 있습니다.

이 답변으로 도움이 되었기를 바랍니다.