与通配符匹配的文件名

Question

我需要实现类似我自己的文件系统的东西。一个操作是 FindFirstFile。我需要检查调用者是否通过了类似 . , 样本*.cpp 左右。我的“文件系统”实现将“文件名”列表作为 char* 数组提供。

是否有任何 Windows 函数或任何实现此文件名匹配的源代码？

原文由 harper 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

周围有很多这样的功能。这是各种实现的 目录，分为递归和非递归等。

如果您不喜欢那里的许可（或链接有问题等），这是匹配算法的一种可能实现，该算法至少接近 Windows 使用的算法：

 #include <string.h>
#include <iostream>

bool match(char const *needle, char const *haystack) {
    for (; *needle != '\0'; ++needle) {
        switch (*needle) {
        case '?':
            if (*haystack == '\0')
                return false;
            ++haystack;
            break;
        case '*': {
            if (needle[1] == '\0')
                return true;
            size_t max = strlen(haystack);
            for (size_t i = 0; i < max; i++)
                if (match(needle + 1, haystack + i))
                    return true;
            return false;
        }
        default:
            if (*haystack != *needle)
                return false;
            ++haystack;
        }
    }
    return *haystack == '\0';
}

#ifdef TEST
#define CATCH_CONFIG_MAIN

#include "catch.hpp"

TEST_CASE("Matching", "[match]") {
    REQUIRE(match("a", "a") == true);
    REQUIRE(match("a", "b") == false);
    REQUIRE(match("a*", "a") == true);
    REQUIRE(match("a?", "a") == false);
    REQUIRE(match("a?", "ab") == true);
    REQUIRE(match("a*b", "ab") == true);
    REQUIRE(match("a*b", "acb") == true);
    REQUIRE(match("a*b", "abc") == false);
    REQUIRE(match("*a*??????a?????????a???????????????",
        "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa") == true);
}

#endif

由于讨论了其他一些答案的复杂性，我会注意到我相信这具有 O(NM) 复杂性和 O(M) 存储使用（其中 N 是目标字符串的大小，M 是图案的大小）。

使用@masterxilo 的测试对：

 "*a*??????*a*?????????a???????????????", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

…这会在我的机器上大约 3 微秒内找到匹配项。这 比 典型的模式要慢得多——我的大多数其他测试在这台特定的机器上运行大约 300 纳秒左右。

同时，@masterxilo 的代码在同一台机器上运行大约需要 11 微秒，所以这仍然快了大约 3 到 4 倍（更不用说更小更简单了）。

原文由 Jerry Coffin 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

这是一个无依赖的可移植 C++ 版本：

 #include <string>

#include <string.h>

bool wild_match(const std::string& str, const std::string& pat) {
  std::string::const_iterator str_it = str.begin();
  for (std::string::const_iterator pat_it = pat.begin(); pat_it != pat.end();
       ++pat_it) {
    switch (*pat_it) {
      case '?':
        if (str_it == str.end()) {
          return false;
        }

        ++str_it;
        break;
      case '*': {
        if (pat_it + 1 == pat.end()) {
          return true;
        }

        const size_t max = strlen(&*str_it);
        for (size_t i = 0; i < max; ++i) {
          if (wild_match(&*(pat_it + 1), &*(str_it + i))) {
            return true;
          }
        }

        return false;
      }
      default:
        if (*str_it != *pat_it) {
          return false;
        }

        ++str_it;
    }
  }

  return str_it == str.end();
}

原文由 ericcurtin 发布，翻译遵循 CC BY-SA 4.0 许可协议