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

Question

다음 문자열을 예로 들어 보겠습니다.

"빠른 갈색 여우"

현재 Quick의 q는 문자열의 인덱스 4(0에서 시작)에 있고 fox의 f는 인덱스 16에 있습니다.이제 사용자가 이 문자열에 추가 텍스트를 입력한다고 가정해 보겠습니다.

"매우 빠른 암갈색 여우"

이제 q는 인덱스 9에 있고 f는 인덱스 26에 있습니다.

사용자가 몇 개의 문자를 추가하더라도 Quick의 원본 q와 fox의 f의 인덱스를 추적하는 가장 효율적인 방법은 무엇입니까?

언어는 나에게 중요하지 않습니다. 이것은 무엇보다 이론적인 질문에 가깝습니다. 따라서 원하는 언어를 사용하고 일반적으로 인기 있고 현재 언어로 유지하려고 노력하십시오.

제가 제공한 샘플 문자열은 짧지만 모든 크기의 문자열을 효율적으로 처리할 수 있는 방법이 있기를 바랍니다.따라서 오프셋을 사용하여 배열을 업데이트하면 짧은 문자열에서는 작동하지만 많은 문자로 인해 정체됩니다.

비록 예제에서는 문자열의 고유 문자 인덱스를 찾고 있었지만 갈색의 o와 여우의 o와 같이 다른 위치에서 동일한 문자의 인덱스를 추적할 수도 있기를 원합니다.그래서 검색은 불가능합니다.

나는 대답이 시간과 메모리 모두 효율적이기를 바랐지만 하나만 선택해야 한다면 성능 속도가 더 중요합니다.

Answer 1

문자열이 있고 그 문자 중 일부가 다음과 같다고 가정해 보겠습니다. 흥미로운.일을 더 쉽게 하기 위해 인덱스 0에 있는 문자는 항상 흥미롭고 그 앞에는 센티넬이라는 것을 추가하지 않는다고 가정해 보겠습니다.(흥미로운 문자, 이전의 흥미로운 문자까지의 거리) 쌍을 적어보세요.문자열이 "+the Very Quick dark brown Fox"이고 'quick'의 q와 'fox'의 f에 관심이 있는 경우 다음과 같이 작성합니다.(+,0), (q,10), (f,17).(기호 +는 센티넬입니다.)

이제 이를 순차 순회를 통해 문자열에 나타나는 순서대로 문자 시퀀스를 제공하는 균형 잡힌 이진 트리에 넣습니다.이제 당신은 부분합 문제:노드에 (문자, 거리, 합계)가 포함되도록 트리를 강화합니다.합은 왼쪽 하위 트리에 있는 모든 거리의 합입니다.(따라서 합(x)=거리(왼쪽(x))+합(왼쪽(x)).)

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

추가했다고 하니까 N 문자 왼쪽의 문자 씨 distance(c)+=n이라고 말한 다음 모든 부모의 합계를 업데이트합니다. 씨.

지수가 무엇인지 물어보려면 씨 당신은 sum(c)+sum(parent(c))+sum(parent(parent(c)))+...를 계산합니다.

Answer 2

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

문자열의 인덱스보다 낮은 위치에 텍스트를 삽입할 때마다 삽입된 문자열의 길이를 기준으로 오프셋을 계산하면 됩니다.

Answer 3

모든 데이터 구조와 상호 작용이 모든 언어에서 동일하게 효율적이고 효과적인 것은 아니기 때문에 대상 언어를 염두에 두고 있다면 도움이 될 것입니다.

Answer 4

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

이 구조에 문자를 삽입하거나 삭제하려면 O(log(N)) 작업(루트 경로의 비트맵 업데이트)만 필요하며 문자가 처음 나타나는 경우에도 O(log(N)) 작업이 필요합니다. 비트맵에 흥미로운 문자가 포함된 가장 왼쪽 자식으로 이동합니다.

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