Существует ли известный O (nm )-время/O (1 )-пространство алгоритм для сопоставления имен файлов POSIX (fnmatch )?

Редактировать:УПАХ! Большое признание, я напортачил с определением синтаксиса шаблона ?в fnmatchи, кажется, предложил (и, возможно, решил )гораздо более сложную проблему, где он ведет себя как .?в регулярных выражениях. Конечно, на самом деле предполагается, что он ведет себя как .в регулярных выражениях (, соответствующих ровно одному символу, а не нулю или одному ). Что, в свою очередь, означает, что моей первоначальной -работы по редукции было достаточно, чтобы решить (уже довольно скучную )исходную задачу. Тем не менее, решение более сложной задачи довольно интересно; Может когда-нибудь напишу.

С положительной стороны, это означает, что гораздо больше шансов, что что-то вроде 2way/SMOA игольчатой ​​факторизации может быть применимо к этим шаблонам, что, в свою очередь, может дать лучший -, чем -первоначально -желаемый O(n)или даже O(n/m)производительности.

В заголовке вопроса пусть mбудет длиной шаблона/иглы, а nбудет длиной строки, с которой он сопоставляется.

Этот вопрос представляет для меня интерес, потому что все алгоритмы, которые я видел/использовал, имеют либо патологически низкую производительность и возможные эксплойты переполнения стека из-за поиска с возвратом, либо требуют динамического выделения памяти (, например. для подхода DFA или просто избегать возврата в стеке вызовов )и, таким образом, иметь случаи сбоя, которые также могут быть опасными, если программа использует fnmatchдля предоставления/отказа прав доступа какого-либо рода.

Я готов поверить, что такого алгоритма для сопоставления регулярных выражений не существует, но язык шаблонов имен файлов намного проще, чем регулярные выражения. Я уже упростил задачу до такой степени, что можно предположить, что шаблон не использует символ *, и в этой модифицированной задаче вы не сопоставляете всю строку, а ищете вхождение шаблона в строку (как проблема соответствия подстроки ). Если вы еще больше упростите язык и удалите символ ?, язык просто состоит из конкатенаций фиксированных строк и выражений в квадратных скобках, и это можно легко сопоставить за время O(mn)и O (1 )пространство, который, возможно, может быть улучшен до O(n), если методы игольчатой ​​факторизации, используемые в двустороннем поиске и поиске подстроки SMOA, могут быть расширены на такие шаблоны скобок. Однако наивно каждый ?требует испытаний с или без использования ?символа, что приводит к фактору времени 2^q, где q— количество ?символов в шаблоне.

Кто-нибудь знает, эта проблема уже решена?или есть идеи по ее решению?

Примечание :При определении пространства O (1 )я использую Трансдихотомическую _модель .

Примечание 2 :На этом сайте есть подробная информация об алгоритмах 2way и SMOA, на которые я ссылался:http://www-igm.univ-mlv.fr/~lecroq/string/index.html