我目前正在研究UNIX式全局模式匹配的实现。通常，fnmatch库是该功能的很好的参考实现。用于全局模式匹配的递归解决方案
看一些the implementations，以及阅读各种关于这个博客/教程，似乎这个算法通常是递归实现。
一般来说，任何需要“回溯”或需要返回到较早状态的算法都很适合递归解决方案。这包括树遍历或解析嵌套结构等内容。
但我很难理解为什么glob模式匹配特别是经常递归实现。我的想法，有时回追踪将是必要的，例如，如果我们有一个字符串aabaabxbaab和图案a*baab，在*后的字符将匹配第一个“BAAB”子，像aa(baab)xbaab，然后无法匹配字符串的其余部分。所以算法将需要回溯，以便字符匹配计数器重新开始，并且我们可以匹配第二次出现baab，如：aabaabx(baab)。
好，但一般递归使用时，我们可能需要回溯的多个嵌套的水平，我不明白怎么会在这种情况下是必要的。看起来我们只需要一次回溯一个级别，当模式上的迭代器和输入字符串上的迭代器不匹配时。此时，模式上的迭代器需要移回到最后一个“保存点”，该保存点可以是字符串的开头，也可以是最后成功匹配某个内容的最后一个“保存点”。这不需要堆叠 - 只需要一个保存点。
我能想到的唯一复杂情况就是发生“重叠”匹配。例如，如果我们有输入字符串aabaabaab和模式a*baab，我们将无法匹配，因为最后一个baab中的“b”可能是第一个匹配或第二个匹配的一部分。但是，如果最后一个模式迭代器保存点和模式结束之间的距离大于输入迭代器位置和输入字符串结尾之间的距离，则可以通过简单地回溯输入迭代器来解决这个问题。
所以，就我所看到的，迭代实现这个全局匹配算法应该不是一个太大的问题（假设一个非常简单的glob匹配器，它只使用*字符表示“匹配零。或多个字符”另外，匹配策略将是贪婪）
所以，我想我肯定对这种错误，因为其他人都做这个递归 - 所以我必须失去了一些东西。这只是我看不到我在这里失去的东西。所以我在C++中实现了一个简单的glob匹配器（仅支持*运算符），以查看我是否能够找出我错过的东西。这是一个非常直接，简单的迭代解决方案，它只是使用内部循环来执行通配符匹配。它也记录该*字符对的向量匹配指数：
bool match_pattern(const std::string& pattern, const std::string& input,
std::vector<std::pair<std::size_t, std::size_t>>& matches)
{
const char wildcard = '*';
auto pat = std::begin(pattern);
auto pat_end = std::end(pattern);
auto it = std::begin(input);
auto end = std::end(input);
while (it != end && pat != pat_end)
{
const char c = *pat;
if (*it == c)
{
++it;
++pat;
}
else if (c == wildcard)
{
matches.push_back(std::make_pair(std::distance(std::begin(input), it), 0));
++pat;
if (pat == pat_end)
{
matches.back().second = input.size();
return true;
}
auto save = pat;
std::size_t matched_chars = 0;
while (it != end && pat != pat_end)
{
if (*it == *pat)
{
++it;
++pat;
++matched_chars;
if (pat == pat_end && it != end)
{
pat = save;
matched_chars = 0;
// Check for an overlap and back up the input iterator if necessary
//
std::size_t d1 = std::distance(it, end);
std::size_t d2 = std::distance(pat, pat_end);
if (d2 > d1) it -= (d2 - d1);
}
}
else if (*pat == wildcard)
{
break;
}
else
{
if (pat == save) ++it;
pat = save;
matched_chars = 0;
}
}
matches.back().second = std::distance(std::begin(input), it) - matched_chars;
}
else break;
}
return it == end && pat == pat_end;
}
然后我写了一系列的测试，看看如果我能找到一些图案或输入字符串需要回溯的多个级别（和因此递归或栈），但我似乎无法想出任何东西。
这里是我的测试功能：
void test(const std::string& input, const std::string& pattern)
{
std::vector<std::pair<std::size_t, std::size_t>> matches;
bool result = match_pattern(pattern, input, matches);
auto match_iter = matches.begin();
std::cout << "INPUT: " << input << std::endl;
std::cout << "PATTERN: " << pattern << std::endl;
std::cout << "INDICES: ";
for (auto& p : matches)
{
std::cout << "(" << p.first << "," << p.second << ") ";
}
std::cout << std::endl;
if (result)
{
std::cout << "MATCH: ";
for (std::size_t idx = 0; idx < input.size(); ++idx)
{
if (match_iter != matches.end())
{
if (idx == match_iter->first) std::cout << '(';
else if (idx == match_iter->second)
{
std::cout << ')';
++match_iter;
}
}
std::cout << input[idx];
}
if (!matches.empty() && matches.back().second == input.size()) std::cout << ")";
std::cout << std::endl;
}
else
{
std::cout << "NO MATCH!" << std::endl;
}
std::cout << std::endl;
}
我的实际测试：
test("aabaabaab", "a*b*ab");
test("aabaabaab", "a*");
test("aabaabaab", "aa*");
test("aabaabaab", "aaba*");
test("/foo/bar/baz/xlig/fig/blig", "/foo/*/blig");
test("/foo/bar/baz/blig/fig/blig", "/foo/*/blig");
test("abcdd", "*d");
test("abcdd", "*d*");
test("aabaabqqbaab", "a*baab");
test("aabaabaab", "a*baab");
所以这个输出：
INPUT: aabaabaab
PATTERN: a*b*ab
INDICES: (1,2) (3,7)
MATCH: a(a)b(aaba)ab
INPUT: aabaabaab
PATTERN: a*
INDICES: (1,9)
MATCH: a(abaabaab)
INPUT: aabaabaab
PATTERN: aa*
INDICES: (2,9)
MATCH: aa(baabaab)
INPUT: aabaabaab
PATTERN: aaba*
INDICES: (4,9)
MATCH: aaba(abaab)
INPUT: /foo/bar/baz/xlig/fig/blig
PATTERN: /foo/*/blig
INDICES: (5,21)
MATCH: /foo/(bar/baz/xlig/fig)/blig
INPUT: /foo/bar/baz/blig/fig/blig
PATTERN: /foo/*/blig
INDICES: (5,21)
MATCH: /foo/(bar/baz/blig/fig)/blig
INPUT: abcdd
PATTERN: *d
INDICES: (0,4)
MATCH: (abcd)d
INPUT: abcdd
PATTERN: *d*
INDICES: (0,3) (4,5)
MATCH: (abc)d(d)
INPUT: aabaabqqbaab
PATTERN: a*baab
INDICES: (1,8)
MATCH: a(abaabqq)baab
INPUT: aabaabaab
PATTERN: a*baab
INDICES: (1,5)
MATCH: a(abaa)baab
，经过"MATCH: "显示出现在输出中的括号每个*匹配/消耗的子字符串字符。所以，这似乎工作正常，我似乎无法理解为什么有必要在这里回溯多个级别 - 至少如果我们限制我们的模式只允许*个字符，并且我们假定贪婪匹配。
所以我认为我肯定是错误的，可能会忽略一些简单的东西 - 有人可以帮我看看为什么这个算法可能需要多级回溯（因此递归或堆栈）？
这似乎是一个很好的方法，如果您可以共享一个不记录索引的版本（可能不会备份迭代器）并因此进行了优化，那么这对分析的原因会很有帮助。 针对AI作品的递归版本进行性能测试，让我感受到了这一点，非常感谢您。 –
你的算法似乎声称'daaadabadmanda'不符合'da * da * da *'模式。有时我们选择递归只是因为它更容易使算法正确。 https://www.youtube.com/watch?v=lNYcviXK4rg –