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

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). (Знак + - это страж.)

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

Answer 2

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

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

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

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

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

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

Answer 3

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

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

Answer 4

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

Answer 5

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

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

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