Какой самый эффективный способ отслеживать индекс конкретного символа в строке?
-
09-06-2019 - |
Вопрос
Возьмем следующую строку в качестве примера:
" Быстрая коричневая лиса " Р>
Прямо сейчас q в quick находится в индексе 4 строки (начиная с 0), а f в fox - в индексе 16. Теперь предположим, что пользователь вводит еще немного текста в эту строку.
" Очень быстрая темно-коричневая лиса "
Теперь q имеет индекс 9, а f индекс 26.
Какой самый эффективный метод отслеживания индекса исходного q в быстрой и f в лисе независимо от того, сколько символов добавлено пользователем?
Язык не имеет значения для меня, это больше вопрос теории, чем что-либо, поэтому используйте любой язык, который вы хотите, просто постарайтесь сохранить его на общедоступных и современных языках.
Пример строки, которую я дал, короток, но я надеюсь на способ, который может эффективно обработать строку любого размера. Таким образом, обновление массива со смещением будет работать с короткой строкой, но с большим количеством символов. Р>
Несмотря на то, что в примере я искал индекс уникальных символов в строке, я также хочу иметь возможность отслеживать индекс одного и того же символа в разных местах, таких как o в коричневом цвете и o в лисице. Так что о поиске не может быть и речи.
Я надеялся, что ответ будет эффективным и по времени, и по памяти, но если мне нужно было выбрать только один, меня больше заботит скорость работы.
Решение
Допустим, у вас есть строка и некоторые ее буквы интересны . Чтобы упростить ситуацию, скажем, что буква с индексом 0 всегда интересна, и вы никогда не добавляете что-либо перед ней - часового. Запишите пары (интересное письмо, расстояние до предыдущего интересного письма). Если строка "+ очень быстрый темно-коричневый лис" и вас интересуют q из «quick» и f из «fox», тогда вы бы написали: (+, 0), (q, 10), (f, 17). (Знак + - это страж.)
Теперь вы помещаете их в сбалансированное двоичное дерево, чей обход по порядку дает последовательность букв в порядке их появления в строке. Теперь вы можете распознать
Другие советы
Ваш вопрос немного двусмысленный - хотите ли вы отслеживать первые экземпляры каждой буквы? В этом случае наилучшим вариантом может быть массив длины 26.
Всякий раз, когда вы вставляете текст в строку в позиции, которая ниже вашего индекса, просто рассчитывайте смещение на основе длины вставленной строки.
Было бы также полезно, если бы вы имели в виду целевой язык, поскольку не все структуры данных и взаимодействия одинаково эффективны и действенны во всех языках. Р>
Стандартный прием, который обычно помогает в подобных ситуациях, состоит в том, чтобы сохранить символы строки в виде листьев в сбалансированном двоичном дереве. Кроме того, внутренние узлы дерева должны хранить наборы букв (если алфавит маленький и фиксированный, они могут быть растровыми изображениями), которые встречаются в поддереве с корнем в конкретном узле.
Для вставки или удаления буквы в эту структуру требуются только операции O (log (N)) (обновить растровые изображения на пути к корню), а для поиска первого вхождения буквы также требуются операции O (log (N)) - Вы спускаетесь из корня, выбирая самого левого ребенка, чье растровое изображение содержит интересную букву.
Редактировать: внутренние узлы также должны хранить количество листов в представленном поддереве для эффективного вычисления индекса буквы.