Как Вы говорите, накладываются ли два подстановочных знака?
Учитывая две строки с * подстановочные знаки, я хотел бы знать, могла ли строка быть создана, который соответствовал бы обоим.
Например, эти два являются простым случаем перекрытия:
- Hello*World
- Hel*
Но так все они:
- *.csv
- reports*.csv
- reportsdump.csv
Существует ли алгоритм, опубликованный для того, чтобы сделать это? Или возможно служебная функция в Windows или библиотеке я смог называть или копировать?
1 ответ
Поскольку каждый глобус можно записать в виде регулярного выражения, а пересечение двух регулярных выражений можно найти (если только они не являются регулярными, но в данном случае это так), вы можете найти пересечение двух глобусов, преобразовав их в регулярные выражения, а затем найдя их пересечение. Таким образом, вы можете узнать, пересекаются ли две глобулы, найдя пересечение регулярных выражений и проверив, пусто ли оно.
Однако, поскольку глобы более ограничены, чем регулярные выражения, существует гораздо более простой способ:
Назовем два глоба g1 и g2. Они пересекаются, если
- И g1, и g2 пусты или содержат только подстановочные знаки.
- Ни g1, ни g2 не пусты и одно из следующих условий истинно (пусть c1 - первый символ g1, а t1 - строка, содержащая остальные символы - то же самое для g2 с c2 и t2):
- c1 и c2 равны и t1 и t2 пересекаются
- c1 и/или c2 - подстановочный знак и t1 пересекается с g2
- c1 и/или c2 - подстановочный знак и g1 пересекается с t2
Пример реализации на haskell:
intersect g1 [] = all (== '*') g1
intersect [] g2 = all (== '*') g2
intersect g1@('*':t1) g2@(c2:t2) = intersect g1 t2 || intersect t1 g2
intersect g1@(c1:t1) g2@('*':t2) = intersect t1 g2 || intersect g1 t2
intersect (c1:t1) (c2:t2) = c1 == c2 && intersect t1 t2
Этот алгоритм не особенно эффективен, если глобусы содержат много подстановочных знаков, но он очень прост в реализации, и поскольку вы, скорее всего, планируете использовать его с именами файлов, я сомневаюсь, что у вас будут глобусы длиннее 1000 символов.