Привет.
Наверняка, кто-нибудь тут сталкивался с задачей проверки строки на соответсвие шаблона заданного Wildcard, на манер имен файлов (c:\dir\*\????la*.txt). То есть: * - любое количество символов, ? - один любой символ.
Первое, что мне пришло в голову - это жадный алгоритм решения.
Разделяем всю строку на группы между которыми стоят *. Ищем каждую группу, как можно ближе к началу строки.
Ситуации типа: *??*?* - обрабатываем как одну *, но пропускаем 3 символа в строке.
При поиске последней группы требуем чтобы она находилась в конце строки.
Вот код: http://pastebin.com/ALQa7WmE
И вроде бы, я не могу найти контр-примера. Но в интернете везде лежит либо, некорректный жадный алгоритм, не обрабатывающий ситуации a*? или же динамика. Может кто-нибудь привести контр-пример?
pattern = pattern.replaceAll("\\?", ".").replaceAll("\\*", ".*");
for (String filename : directory) {
if (filename.matches(pattern)) {
process(filename);
} // if
} // for
Но, сейчас у меня нет возможности линковать boost::regex, а включать другую библиотеку ради такой мелочи не хочется.
Кроме того, при использовании регулярных выражений, в зависимоти от типа автомата, ситуации типа *?* могут привести к экспоненциальному времени поиска.
Просто уже интересно, верный у меня жадный алгоритм получился или нет. Плюс, он будет работать без дополнительной памяти при любых размерах строк, и время, в отличие от динамики, может быть значительно меньше квадрата в большинстве случаев.
Ситуации типа: *??*?* - обрабатываем как одну *, но пропускам 3 символа в строке.
Ищем каждую группу, как можно ближе к началу строки. При поиске последней группы требуем чтобы она находилась в конце строки.
Вот код:
http://pastebin.com/ALQa7WmE
Если количество звёздочек и вопросиков не очень большое, то можно сходу написать маленькую рекурсию:
Код на Питоне в первой правке
Там от противного что-то должно рождаться, наверное. Мол предположим, что алгоритм (корректно реализованный) дал некорректное решение.
Т.е. либо он совпал со строкой, с которой не должен -это значит, нашёл в ней лишнюю группу, либо одна из групп ошибочно совпала с чем-то, с чем не должна была (что видимо противоречит предположению о корректной реализации).
Либо он не совпал со строкой, с которой был должен совпасть. И не совпал из-за жадности. Т.е. из-за того, что какая-то группа была замэтчена раньше, чем надо было. Однако, если какую-то группу удалось бы "совпасть" раньше, чем следовало, то остальным группам это не должно было бы помешать совпасть (хотя бы в тех же позициях, в которых они совпали бы при гипотетическом "корректном" алгоритме). Способ размещения последней группы тут не влияет на рассуждения, вроде.
Надо формализовать это дело, получится красивый и наукообразный пост. ;-)