Блог пользователя Ac-93

Автор Ac-93, история, 2 года назад, По-русски

Здравствуйте, столкнулся с такой задачей:

Текст приходит как набор символов онлайн, алфавит может быть большим (до нескольких байт), вместе с символами приходят запросы (с частотой примерно 1 запрос на 10 символов): найти max длину подстроки между (pointer, cur_pos) которая повторяет строку начинающуюся с (pointer).

Например, для строки (abcab[запрос префикса с 0, ответ длина 2, pos 3]cab[запрос префикса с 2, ответ длина 3, pos 5]). Т.е. для первого запроса ищем префикс abcab на участке bcab, находим ab; Для второго запроса ищем префикс cabcab на участке abcab, находим cab.

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

Знает ли кто-то возможно ли решение быстрее? В теории суффиксное дерево позволяет искать max подстроку, но оно тоже кажется медленным, т.е. слишком большая константа в операциях поиска и построения + не совсем ясно как избавиться от вхождений до начала интервала поиска.

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

Если кто-то может дать направление куда копать с такой задачей то буду очень признателен,

Update: о текущем решение, я поддерживаю hash_map[M=20] где ключ это подстрока а значение это позиция где мы последний раз видели подстроку такой длины. В итоге на каждый запрос я проверяю есть ли такая подстрока длины 1, если есть то проверяю 2 и т.д. до 20, после чего возвращаю ответ из самой длинной совпадающей. Сложность M*M в худшем. Когда приходит новый char я обновляю hash_map[1][new_char]=cur_pos, если в hash_map уже была позиция для [new_char] то я пропагандирую ее на длину 2 и так пока не получу уникальное место, тут тоже примерно M операция, в худшем случае M*M. В итоге имею не оптимальный ответ но как минимум длины 20 если такой существует.

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
2 года назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

Ну ты можешь просто бахнуть суф масс от всей строки (она, дана в оффлайне, надеюсь). Затем, когда приходит запрос с позиции pos, когда тебе интересны только позиции <= t, то ты должен просто взять первый элемент слева/справа в суф массе от позиции отвечающую за pos, позиция которых в изначальной строке <= t. И тогда максимум из lcp в этих 2 позициях — это ответ. Ну а это легко делается спуском по ДО, например, то бишь log на запрос

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    нет, строка формируется по мере прихода char-ов.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем Ac-93 (предыдущая версия, новая версия, сравнить).