문자열에서 특정 문자의 색인을 추적하는 가장 효율적인 방법은 무엇입니까?

Question

예로 들어 다음과 같은 문자열을 가지고 :

"빠른 갈색 여우"

는 지금 빠른에서 q는 문자열 (0부터 시작)와 여우의 F의 인덱스 4에있다 인덱스입니다 16. 이제 사용자가이 문자열에 텍스트를 더 입력한다고 가정 해 봅니다.

"매우 빠른 어두운 갈색 여우"

이제 q는 인덱스 9시이며, F는

원래의 인덱스를 추적하는 가장 효율적인 방법은 무엇입니까 인덱스 (26)에있다 사용자가 얼마나 많은 문자를 추가했는지에 상관없이 빠른 f와 여우 f

언어는 나에게 중요하지 않습니다. 이것은 무엇보다 이론적 질문 일 뿐이므로 원하는 언어를 사용하여 일반적으로 인기 있고 최신 언어로 유지하려고합니다.

내가 준 샘플 문자열은 짧지 만 모든 크기 문자열을 효율적으로 처리 할 수있는 방법이 필요합니다. 오프셋을 사용하여 배열을 업데이트하면 짧은 문자열로도 작업 할 수 있지만 많은 문자가 덤프됩니다.

비록 내가 예를 들어 문자열에서 고유 한 문자의 색인을 찾고 있었지만 갈색과 o의 여백 같은 다른 위치에서 동일한 문자의 색인을 추적 할 수 있기를 원합니다. 따라서 검색은 의문의 여지가 없습니다.

나는 대답이 시간과 메모리 모두 효율적이기를 바랬지 만 하나만 선택해야한다면 성능 속도에 더 관심이 있습니다.

Answer 1

문자열이 있고 그 문자 중 일부는 이고 흥미로운 내용은입니다. 일을 더 쉽게 만들려면 인덱스 0에있는 문자가 항상 흥미 롭다고 말하면서 그것 앞에 무언가를 추가하지 마십시오. — 센티널. (재미있는 문자, 이전 재미있는 문자까지의 거리)의 쌍을 써라. 문자열이 "매우 빠른 짙은 갈색 여우"이고 "fox"의 q와 'fox'의 q에 관심이 있다면 (+, 0), (q, 10), (f, 17).

이제 이것을 순서대로 검색하여 문자열에 나타나는 순서대로 문자 시퀀스를 제공하는 균형 이진 트리에 배치합니다. 이제 partial sums problem을 인식 할 수 있습니다. 노드에 (문자, 거리, 합계)가 포함되도록 트리를 향상시킵니다. 합계는 왼쪽 하위 트리의 모든 거리의 합계입니다.

이제이 데이터 구조를 로그 시간으로 쿼리하고 업데이트 할 수 있습니다.

당신이 문자 C의 왼쪽에 N 문자를 추가 말을 당신은 말할 거리 (C) + = n은 다음 가서 C의 모든 부모를위한 업데이트 합. 당신이 합 (C) + 합계 (부모 (C)) + 합계 계산 C의 인덱스 (부모 (부모 (C))) + ...

Answer 2

귀하의 질문은 약간 모호합니다. 모든 편지의 첫 번째 사례를 추적하고 싶습니까? 그렇다면 길이 26의 배열이 가장 좋은 옵션 일 수 있습니다.

색인에있는 문자보다 낮은 위치에 텍스트를 삽입 할 때마다 삽입 된 문자열의 길이에 따라 오프셋을 계산하면됩니다.

Answer 3

모든 언어에서 모든 데이터 구조와 상호 작용이 똑같이 효율적이고 효과적인 것은 아니므로 대상 언어가 있다면 도움이됩니다.

Answer 4

표준 트릭이 무엇인지 물어

유사한 상황에서 일반적으로 도움이되는 것은 문자열의 문자를 균형 잡힌 이진 트리에 나뭇잎으로 유지하는 것입니다. 또한 트리의 내부 노드는 특정 노드를 루트로하는 하위 트리에서 발생하는 문자 집합 (알파벳이 작고 고정 된 경우 비트 맵이 될 수 있음)을 유지해야합니다.

이 구조체에 문자를 삽입하거나 삭제하면 O (log (N)) 연산 (경로의 비트 맵을 root로 업데이트)이 필요하며 문자의 첫 번째 발생을 찾는 작업도 O (log - 비트 맵에 재미있는 문자가 들어있는 가장 왼쪽 자식을 찾으려면 루트에서 내려갑니다.

편집 : 내부 노드는 문자 인덱스의 효율적인 계산을 위해 표현 된 하위 트리의 리프 수를 유지해야합니다.