Какой самый эффективный способ отслеживать индекс конкретного символа в строке?

Question

Взять в качестве примера следующую строку:

"Быстрая коричневая лиса"

Прямо сейчас q в quick находится в индексе 4 строки (начиная с 0), а f в fox - в индексе 16. Теперь предположим, что пользователь вводит еще немного текста в эту строку.

"Очень быстрая темно-коричневая лиса"

Теперь q в индексе 9, а f в индексе 26.

Какой самый эффективный метод отслеживания индекса исходного q в быстрой и f в лисе независимо от того, сколько символов добавлено пользователем?

Язык не имеет значения для меня, это больше вопрос теории, чем что-либо, поэтому используйте любой язык, который вы хотите, просто попытайтесь сохранить его на общедоступных и современных языках.

Пример строки, которую я дал, короток, но я надеюсь на способ, который может эффективно обрабатывать строки любого размера. Таким образом, обновление массива со смещением будет работать с короткой строкой, но с большим количеством символов.

Несмотря на то, что в примере я искал индекс уникальных символов в строке, я также хочу иметь возможность отслеживать индекс одного и того же символа в разных местах, таких как o в коричневом цвете и o в лисице. Так что о поиске не может быть и речи.

Я надеялся, что ответ будет эффективным и по времени, и по памяти, но если мне нужно было выбрать только один, меня больше волнует скорость работы.

Answer 1

Допустим, у вас есть строка, и некоторые ее буквы интересны . Чтобы упростить ситуацию, скажем, что буква с индексом 0 всегда интересна, и вы никогда не добавляете что-либо перед ней - сторож. Запишите пары (интересное письмо, расстояние до предыдущего интересного письма). Если строка «+ очень быстрая темно-коричневая лиса» и вас интересуют q из «quick» и f из «fox», вы должны написать: (+, 0), (q, 10), (f, 17 ). (Знак + является стражем.)

Теперь вы помещаете их в сбалансированное двоичное дерево, чей обход по порядку дает последовательность букв в порядке их появления в строке. Теперь вы можете распознать проблему частичных сумм : вы расширяете дерево, чтобы узлы содержали (буква, расстояние, сумма). Сумма является суммой всех расстояний в левом поддереве. (Следовательно, сумма (x) = расстояние (слева (x)) + сумма (слева (x)).)

Теперь вы можете запрашивать и обновлять эту структуру данных в логарифмическом времени.

Чтобы сказать, что вы добавили n символов слева от символа c вы говорите расстояние (c) + = n a, затем идите и обновите сумму для всех родителей с .

Чтобы спросить, каков индекс c , вы вычисляете сумму (c) + sum (parent (c)) + sum (parent (parent (c))) + + ...

Answer 2

Ваш вопрос немного двусмысленный - вы ищете, чтобы отслеживать первые экземпляры каждой буквы? В таком случае наилучшим вариантом может быть массив длиной 26

.

Всякий раз, когда вы вставляете текст в строку в позиции, которая меньше, чем у вашего индекса, просто вычисляйте смещение на основе длины вставленной строки.

Answer 3

Было бы также полезно, если бы вы имели в виду целевой язык, поскольку не все структуры данных и взаимодействия одинаково эффективны и действенны на всех языках.

Answer 4

Стандартный прием, который обычно помогает в подобных ситуациях, состоит в том, чтобы сохранить символы строки в виде листьев в сбалансированном двоичном дереве. Кроме того, внутренние узлы дерева должны хранить наборы букв (если алфавит маленький и фиксированный, они могут быть растровыми изображениями), которые встречаются в поддереве с корнем в конкретном узле.

Для вставки или удаления буквы в этой структуре требуются только операции O (log (N)) (обновить растровые изображения на пути к корню), а для поиска первого вхождения буквы также требуются операции O (log (N)) Вы спускаетесь из корня, выбирая самого левого ребенка, чье растровое изображение содержит интересную букву.

Редактировать: Внутренние узлы должны также хранить количество листьев в представленном поддереве для эффективного вычисления индекса буквы.