我目前正在研究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 –