Самый эффективный алгоритм для нахождения первого соответствия префикса от отсортированного массива строк?
6 ответов
Если Вы только захотите сделать это однажды, используйте двоичный поиск , если, с другой стороны, необходимо сделать это для многих различных префиксов, но на том же массиве строк, создавая дерево основания может быть хорошей идеей после создания дерева, которое каждый ищет, то будет очень быстро.
Это может быть сделано в линейное время с помощью Суффиксное дерево . Создание суффиксного дерева занимает время.
Это - просто измененный поиск деления пополам:
- Только проверка столько символов в каждом элементе, сколько находятся в строке поиска; и
- при нахождении соответствия продолжайте искать назад (или линейно или дальнейшими поисками деления пополам), пока Вы не находите результат несоответствия и затем возвращаете индекс последнего результата соответствия.
Ядро FreeBSD использует дерево Основания для его таблицы маршрутизации, необходимо проверить это.
Вы находитесь в положении для предварительного вычисления всех возможных префиксов?
Если так, можно сделать это, затем использовать двоичный поиск для нахождения префикса в предрасчетной таблице. Сохраните нижний индекс к требуемому значению с префиксом.
Мое текущее решение в памяти, вместо найти "префикс", попытаться найти "виртуальный префикс".
, Например, префикс является “abd", попытайтесь найти виртуальный префикс “abc (255)". (255) просто представляет макс. символьное число. После определения местоположения "abc (255)". Следующее слово должно быть первым словом, соответствующим "abd" если таковые имеются.