Здравствуйте, столкнулся с такой задачей:↵
↵
Текст приходит как набор символов онлайн, алфавит может быть большим (до нескольких байт), вместе с символами приходят запросы (с частотой примерно 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 если такой существует.
↵
Текст приходит как набор символов онлайн, алфавит может быть большим (до нескольких байт), вместе с символами приходят запросы (с частотой примерно 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 если такой существует.
