Qual é a maneira mais eficiente de acompanhar o índice de um caractere específico em uma string?

Question

Tome a seguinte string como exemplo:

"A rápida Raposa marrom"

Neste momento o q em quick está no índice 4 da string (começando em 0) e o f em fox está no índice 16.Agora digamos que o usuário insira mais algum texto nesta string.

"A raposa marrom escura muito rápida"

Agora o q está no índice 9 e o f está no índice 26.

Qual é o método mais eficiente de acompanhar o índice do q original no quick e f no fox, não importa quantos caracteres sejam adicionados pelo usuário?

O idioma não importa para mim, isso é mais uma questão teórica do que qualquer outra coisa, então use o idioma que quiser, apenas tente mantê-lo em idiomas geralmente populares e atuais.

A string de amostra que forneci é curta, mas espero uma maneira que possa lidar com eficiência com strings de qualquer tamanho.Portanto, atualizar uma matriz com o deslocamento funcionaria com uma string curta, mas atrapalharia muitos caracteres.

Embora no exemplo eu estivesse procurando o índice de caracteres únicos na string, também quero poder rastrear o índice do mesmo caractere em locais diferentes, como o em marrom e o em raposa.Portanto, pesquisar está fora de questão.

Eu esperava que a resposta fosse eficiente em termos de tempo e memória, mas se eu tivesse que escolher apenas uma, me preocupo mais com a velocidade de desempenho.

Answer 1

Digamos que você tenha uma string e algumas de suas letras sejam interessante.Para facilitar as coisas, digamos que a letra no índice 0 é sempre interessante e você nunca adiciona algo antes dela – uma sentinela.Escreva pares de (letra interessante, distância da letra interessante anterior).Se a string for "+ the very Quick dark brown Fox" e você estiver interessado em q de 'quick' ef de 'fox' então você escreveria:(+,0), (q,10), (f,17).(O sinal + é a sentinela.)

Agora você os coloca em uma árvore binária balanceada, cujo percurso em ordem fornece a sequência de letras na ordem em que aparecem na string.Você agora pode reconhecer o problema de somas parciais:Você aprimora a árvore para que os nós contenham (letra, distância, soma).A soma é a soma de todas as distâncias na subárvore esquerda.(Portanto soma(x)=distância(esquerda(x))+soma(esquerda(x)).)

Agora você pode consultar e atualizar esta estrutura de dados em tempo logarítmico.

Para dizer que você adicionou n caracteres à esquerda do personagem c você diz distância(c)+=n e então atualiza a soma para todos os pais de c.

Para perguntar qual é o índice de c você calcula sum(c)+sum(parent(c))+sum(parent(parent(c)))+...

Answer 2

Sua pergunta é um pouco ambígua - você deseja acompanhar as primeiras ocorrências de cada carta?Nesse caso, uma matriz de comprimento 26 pode ser a melhor opção.

Sempre que você inserir texto em uma string em uma posição inferior ao índice que você possui, apenas calcule o deslocamento com base no comprimento da string inserida.

Answer 3

Também ajudaria se você tivesse um idioma alvo em mente, pois nem todas as estruturas e interações de dados são igualmente eficientes e eficazes em todos os idiomas.

Answer 4

O truque padrão que geralmente ajuda em situações semelhantes é manter os caracteres da string como folhas em uma árvore binária balanceada.Além disso, os nós internos da árvore devem manter conjuntos de letras (se o alfabeto for pequeno e fixo, podem ser bitmaps) que ocorrem na subárvore com raiz em um determinado nó.

Inserir ou excluir uma letra nesta estrutura requer apenas operações O(log(N)) (atualizar os bitmaps no caminho para a raiz) e encontrar a primeira ocorrência de uma letra também requer operações O(log(N)) - você desce de a raiz, indo para o filho mais à esquerda cujo bitmap contém a letra interessante.

Editar:Os nós internos também devem manter o número de folhas na subárvore representada, para cálculo eficiente do índice da letra.