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