¿Cuál es la forma más eficaz de realizar un seguimiento del índice de un carácter específico en una cadena?

Question

Tome la siguiente cadena como ejemplo:

"El veloz zorro marrón"

En este momento, la q en quick está en el índice 4 de la cadena (comenzando en 0) y la f en fox está en el índice 16.Ahora digamos que el usuario ingresa más texto en esta cadena.

"El veloz zorro marrón oscuro"

Ahora la q está en el índice 9 y la f está en el índice 26.

¿Cuál es el método más eficaz para realizar un seguimiento del índice del q original en quick yf en fox sin importar cuántos caracteres agregue el usuario?

El idioma no me importa, esto es más una pregunta teórica que cualquier otra cosa, así que usa el idioma que quieras, solo trata de mantenerlo en idiomas generalmente populares y actuales.

La cadena de muestra que proporcioné es corta, pero espero encontrar una forma que pueda manejar de manera eficiente cadenas de cualquier tamaño.Por lo tanto, actualizar una matriz con el desplazamiento funcionaría con una cadena corta pero se atascaría con demasiados caracteres.

Aunque en el ejemplo estaba buscando el índice de caracteres únicos en la cadena, también quiero poder rastrear el índice del mismo carácter en diferentes ubicaciones, como la o en marrón y la o en zorro.Así que la búsqueda está fuera de discusión.

Esperaba que la respuesta fuera eficiente tanto en tiempo como en memoria, pero si tuviera que elegir solo una, me preocuparía más la velocidad del rendimiento.

Answer 1

Digamos que tienes una cadena y algunas de sus letras son interesante.Para facilitar las cosas, digamos que la letra en el índice 0 siempre es interesante y nunca se agrega algo antes: un centinela.Anota pares de (letra interesante, distancia a la letra interesante anterior).Si la cadena es "+el zorro marrón oscuro muy rápido" y estás interesado en q de 'rápido' y f de 'zorro' entonces escribirías:(+,0), (q,10), (f,17).(El signo + es el centinela).

Ahora los coloca en un árbol binario equilibrado cuyo recorrido en orden proporciona la secuencia de letras en el orden en que aparecen en la cadena.Quizás ahora reconozcas el problema de sumas parciales:Mejora el árbol para que los nodos contengan (letra, distancia, suma).La suma es la suma de todas las distancias en el subárbol izquierdo.(Por lo tanto suma(x)=distancia(izquierda(x))+suma(izquierda(x)).)

Ahora puede consultar y actualizar esta estructura de datos en tiempo logarítmico.

Para decir que agregaste norte caracteres a la izquierda del personaje C dices distancia (c) + = n y luego vas y actualizas la suma para todos los padres de C.

Para preguntar cuál es el índice de C calculas suma(c)+suma(padre(c))+suma(padre(padre(c)))+...

Answer 2

Su pregunta es un poco ambigua: ¿está buscando realizar un seguimiento de las primeras instancias de cada letra?Si es así, una matriz de longitud 26 podría ser la mejor opción.

Siempre que inserte texto en una cadena en una posición inferior al índice que tiene, simplemente calcule el desplazamiento en función de la longitud de la cadena insertada.

Answer 3

También sería útil tener en mente un idioma de destino, ya que no todas las estructuras de datos e interacciones son igualmente eficientes y efectivas en todos los idiomas.

Answer 4

El truco estándar que suele ayudar en situaciones similares es mantener los caracteres de la cadena como hojas en un árbol binario equilibrado.Además, los nodos internos del árbol deben mantener conjuntos de letras (si el alfabeto es pequeño y fijo, podrían ser mapas de bits) que aparecen en el subárbol con raíz en un nodo particular.

Insertar o eliminar una letra en esta estructura solo necesita operaciones O(log(N)) (actualizar los mapas de bits en la ruta a la raíz) y encontrar la primera aparición de una letra también requiere operaciones O(log(N)); la raíz, yendo al hijo más a la izquierda cuyo mapa de bits contiene la letra interesante.

Editar:Los nodos internos también deben mantener el número de hojas en el subárbol representado, para un cálculo eficiente del índice de letras.