Комментарии 5
Интересная задача.
Если ограничится только одной "*" в шаблоне, то очевидно, что можно легко проверить на совпадение с запросом отдельно префикс до и суффикс после "*" для каждого шаблона. Вопрос в том, как можно сравнивать со всеми шаблонами сразу.
Вот как ваш алгоритм обрабатывает два шаблона "abc*ff" и "abcdef"?
Я правильно понял, что на строке "abcdxf", после поглощения "abc" алгоритм пойдет сразу в обе ветки — и по "f" с конца и по "d" сначала? Т.е. в худшем случае он может обойти все дерево на каждый запрос?
Вообще, задача очень похожа на вот эту с литкода. Только тут в префиксах и суффиксах есть всякие "?#" — удовлетворяющие одному из некоторых наборов символов.
Вообще, есть известный трюк в таких задачах на суффиксы и перфиксы: вы символы вашего суффикса/префикса используйте поперменно. Из корня дерева будут только символы для префиксов. Из детей корня — первые символы всех суффиксов. Потом опять префиксы и т.д.
Если в каком-то запросе суффикс короче префикса, то соответствующие переходы заменяются на какой-нибудь '\0', означающий, что переход есть, но ничего не потребляет. Полученное таким образом дерево концептуально проще. Не надо помнить, в каком вы сейчас режиме.
Потом, можно строку-запрос перемешать в виде символ-сначала, символ-сконца, второй, предпоследний,… Получите строку в 2 раза длинее, но тут уже не надо думать про начало-конец вообще. Только знать, что вы нашли совпадение, если пришли в допускающую вершину на каком-то префиксе входной строки.
А потом уже для этой задачи сопоставления строки с шаблоном только из нейтральных глобов можно построить НКА, который будет принимать только строки удовлетворяющие какому-то шаблону. А уж дальше его можно детерминизировать и тогда любой запрос будет обрабатываться за O(длина запроса), а не за O(сумма длинн всех шаблонов) в худшем случае, как у вас.
Я правильно понял, что на строке "abcdxf", после поглощения "abc"
алгоритм пойдет сразу в обе ветки — и по "f" с конца и по "d" сначала?
Т.е. в худшем случае он может обойти все дерево на каждый запрос?
Да, так как задача - найти все шаблоны.
У меня тоже есть устойчивое ощущение, что полученную реализацию можно улучшать.
Интересно сравнить время передачи (и затраты CPU/сети) среднего сообщения со временем CPU, затраченным на фильтрацию по шаблонам. При каком количестве шаблонов дешевле передать сообщение, чем фильтровать его.
Публикации
Дерево Киви для поиска шаблонов по тексту