Как проверить соответствие имени файла маске?

#алгоритм

Есть имя файла без пути и маска. Надо проверить, соответствует ли имя данной маске.

Маска может содержать:


? - означает 1 любой символ
* - означает 0 или более любых символов
любые другие символы означают сами себя

    

Ответы

Ответ 1

Задачу можно решить следующим образом (порядок проверок менять нельзя):

bool check(char *s, char *p)
{
char *rs=0, *rp;
while(1)
  if(*p=='*')
    rs=s, rp=++p;
  else if(!*s)
    return !*p;
  else if(*s==*p || *p=='?')
    ++s, ++p;
  else if(rs)
    s=++rs, p=rp;
  else
    return false;
}


Используемые переменные:


s (string) - указатель на проверяемую строку (имя файла). В процессе сравнения сдвигается
на проверяемый символ строки (префикс до него уже проверен).
p (pattern) - шаблон, с которым сверяется строка s. В процессе работы сдвигается
на проверяемый символ шаблона (префикс до него проверен).
rs (return in string) и rp (return in pattern) - куда надо откатиться в строке и
шаблоне. rp ссылается на последнюю проверенную *, rs на часть строки, которую эта звёздочка
уже поглотила.


Обоснование алгоритма:


Единственный символ шаблона, которому может соответствовать пустая строка в имени
- это *, поэтому эта проверка должна быть первой.
Если в шаблоне встретилась *, то мы можем заменить её на подстроку любой длины (от
0 до длины всей оставшейся части строки). Будем перебирать все варианты в порядке увеличения
длины, т. е. пропускать на 1 символ больше после каждой неудачи.
Если в шаблоне есть несколько *, то при неудаче достаточно возврата к последней.
Увеличение числа пропускаемых символов у более ранней * не может улучшить результат,
т. к. подстрока между * уже соответствует участку шаблона, при этом величина сдвига
уменьшиться не может, а её увеличение возможно и за счёт последней *.
Если строка закончилась, то это означает конец проверки. Результат соответствует
тому, достигнут ли конец шаблона. Это объясняется тем, что единственный символ шаблона,
который может что-то изменить - это *. Однако, количество пропущенных символов уменьшить
нельзя, а его увеличение не сможет изменить результат (конец строки будет достигнут
ещё раньше). Кроме того, в шаблоне не могут остаться только *, т. к. проверка конца
строки делается после проверки на * в шаблоне.


PS: Этот алгоритм используется с 2010 года в Ureal Commander'е.


Ответ 2

Маски - это последовательности символов и ?, разделенные *. Например:

aa? * b?b * ?cc * ??d


По этому если написать функцию partial_match, которая сравнивает строку с маской
до первой звездочки (с aa? или b?b), то задача сводится к следующему простому алгоритму:

match(name, mask) {
  // Матчим первую часть маски: "aa?"
  if (!partial_match(name, mask))
    return false; // Выходим если начало строки не совпало.

  while (*mask == '*') { // Перебираем остальные части маски: "* b?b * ?cc ..."
    ++mask;
    // Пробуем матчить строку со следующей частью маски,
    // до первого совпадения или пока строка не закончится.
    while (*name && !partial_match(name, mask)) {
      ++name; // Продвигаем строку вперед при неудаче.
    }
  }
  // Проверям что мы дошли до конца строки до конца маски.
  return !*name && !*mask;
}


На С++ это можно записать следующим образом:

class Matcher {
public:
    Matcher(const char* name, const char* mask) : name(name), mask(mask) {}

    bool match() {
        if (!try_partial_match())
            return false;

        while (*mask == '*') {
            ++mask;
            while (!try_partial_match() && *name != '\0')
                ++name;
        }

        return is_full_match();
    }

private:
    bool is_full_match() const { return *name == '\0' && *mask == '\0'; }

    bool patrial_match() {
        while (*name != '\0' && (*name == *mask || *mask == '?')) {
            ++name;
            ++mask;
        }

        return is_full_match() || *mask == '*';
    }

    bool try_partial_match() {
        auto tmp = *this;
        if (tmp.patrial_match()) {
            *this = tmp;
            return true;
        }
        return false;
    }

    const char* name;
    const char* mask;
};


>>> Код полностью <<<