접미사 트리 ACB 접미사 트리 AB를 이미 가지고있는 경우

Question

최근 접미사 트리에 관한 질문이 있습니다. 문자열 S = AB에 대한 접미어 트리가 이미 있다고 가정합니다. 즉, S는 접두어 A와 접미사 B의 연결입니다. 이제 접미어 트리 U = ACB를 작성하려고합니다. 지금까지이 작업을위한 가장 효율적인 알고리즘은 무엇입니까?

순진한 방법은 O를 다시 작성하는 것입니다.이 작업은 O (| U |) 시간에 완료 할 수 있습니다. 그러나 그것은 S의 접미사 트리의 어떤 정보도 이용하지 않을 것입니다. 우리는 O (| U |)보다 잘 할 수 있습니까? 어쩌면 O (| C |), 즉 C의 접미어 트리를 만드는 것만 큼 좋을까요?

대단히 감사합니다.

Answer 1

Google의 "동적 접미어 트리"에 기반하여, 저는 이것이 적극적인 연구 분야라고 생각합니다. 나는이 주제에 대한 첫 번째 (또는 아마 마지막) 단어가 아닌 종이

Paolo Ferragina and Roberto Grossi, "Fast incremental text editing", Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, pp. 531-540, 1995

을 찾을 수 있었고, 나는 단지 그것의 일부를 미끄러 져 있지만 접미사 나무에 몇 가지 변화를 제시하는 문자열이 삽입, 삭제 또는 변경 될 때 더 나은 시간을 얻을 수 있습니다.

• 데이터 구조 1
  • 모든 POCC의 길이-P 문자열의 발생 찾으려면 : O (p + POCC + 유 * 로그 (p)를 + 로그 n)
  U 자 번째 문자열 삽입 후
  • 는 길이의 문자열을 삽입하려면 : O (S의 * 로그 (N + S))
• 데이터 구조 2
  • 모든 POCC의 길이-P 문자열의 발생 찾으려면 O를 (p * log (p) + pocc + u * (log (p) + log (n/u)))

O (S *의 로그 (들) + U 로그)

는 길이의 문자열을 삽입하려면