使用您非常简化的模式语言，您的问题中的 pastebin 链接和 jpmc26 的评论几乎一直存在：主要问题是，您的输入字符串的左端和右端是否匹配。如果他们这样做，并且都包含至少一个*，则字符串匹配（因为您始终可以将其他字符串中间文字文本与该星匹配）。有一种特殊情况：如果其中只有一个是空的（去掉前缀和后缀），如果另一个完全由*s 组成，它们仍然可以匹配。
当然，在检查字符串的结尾是否匹配时，还需要考虑单字符通配符?和字符类。单字符通配符很简单：它不会失败，因为它总是匹配另一个字符。如果是一个字符类，而另一个只是一个字符，则需要检查该字符是否在该类中。如果它们都是类，则需要检查类的交集（这是一个简单的集合交集）。
以下是 JavaScript 中的所有内容（查看代码注释，了解我上面概述的算法如何映射到代码）：
var trueInput = [
{ left: 'prefix*', right: 'prefix:extended*' },
{ left: '*suffix', right: '*:extended:suffix' },
{ left: 'left*right', right: 'left*middle*right' },
{ left: 'a*b*c', right: 'a*b*d*b*c' },
{ left: 'hello*', right: '*ok' },
{ left: '*', right: '*'},
{ left: '*', right: '**'},
{ left: '*', right: ''},
{ left: '', right: ''},
{ left: 'abc', right: 'a*c'},
{ left: 'a*c', right: 'a*c'},
{ left: 'a[bc]d', right: 'acd'},
{ left: 'a[bc]d', right: 'a[ce]d'},
{ left: 'a?d', right: 'acd'},
{ left: 'a[bc]d*wyz', right: 'abd*w[xy]z'},
];
var falseInput = [
{ left: 'prefix*', right: 'wrong:prefix:*' },
{ left: '*suffix', right: '*suffix:wrong' },
{ left: 'left*right', right: 'right*middle*left' },
{ left: 'abc', right: 'abcde'},
{ left: 'abcde', right: 'abc'},
{ left: 'a[bc]d', right: 'aed'},
{ left: 'a[bc]d', right: 'a[fe]d'},
{ left: 'a?e', right: 'acd'},
{ left: 'a[bc]d*wyz', right: 'abc*w[ab]z'},
];
// Expects either a single-character string (for literal strings
// and single-character wildcards) or an array (for character
// classes).
var characterIntersect = function(a,b) {
// If one is a wildcard, there is an intersection.
if (a === '?' || b === '?')
return true;
// If both are characters, they must be the same.
if (typeof a === 'string' && typeof b === 'string')
return a === b;
// If one is a character class, we check that the other
// is contained in the class.
if (a instanceof Array && typeof b === 'string')
return (a.indexOf(b) > -1);
if (b instanceof Array && typeof a === 'string')
return (b.indexOf(a) > -1);
// Now both have to be arrays, so we need to check whether
// they intersect.
return a.filter(function(character) {
return (b.indexOf(character) > -1);
}).length > 0;
};
var patternIntersect = function(a,b) {
// Turn the strings into character arrays because they are
// easier to deal with.
a = a.split("");
b = b.split("");
// Check the beginnings of the string (up until the first *
// in either of them).
while (a.length && b.length && a[0] !== '*' && b[0] !== '*')
{
// Remove the first character from each. If it's a [,
// extract an array of all characters in the class.
aChar = a.shift();
if (aChar == '[')
{
aChar = a.splice(0, a.indexOf(']'));
a.shift(); // remove the ]
}
bChar = b.shift();
if (bChar == '[')
{
bChar = b.splice(0, b.indexOf(']'));
b.shift(); // remove the ]
}
// Check if the two characters or classes overlap.
if (!characterIntersect(aChar, bChar))
return false;
}
// Same thing, but for the end of the string.
while (a.length && b.length && a[a.length-1] !== '*' && b[b.length-1] !== '*')
{
aChar = a.pop();
if (aChar == ']')
{
aChar = a.splice(a.indexOf('[')+1, Number.MAX_VALUE);
a.pop(); // remove the [
}
bChar = b.pop();
if (bChar == ']')
{
bChar = b.splice(b.indexOf('[')+1, Number.MAX_VALUE);
b.pop(); // remove the [
}
if (!characterIntersect(aChar, bChar))
return false;
}
// If one string is empty, the other has to be empty, too, or
// consist only of stars.
if (!a.length && /[^*]/.test(b.join('')) ||
!b.length && /[^*]/.test(b.join('')))
return false;
// The only case not covered above is that both strings contain
// a * in which case they certainly overlap.
return true;
};
console.log('Should be all true:');
console.log(trueInput.map(function(pair) {
return patternIntersect(pair.left, pair.right);
}));
console.log('Should be all false:');
console.log(falseInput.map(function(pair) {
return patternIntersect(pair.left, pair.right);
}));
这不是最简洁的实现，但它可以工作并且（希望）仍然非常可读。检查开头和结尾有相当多的代码重复（reverse在检查开头后可以通过简单的方法来缓解 - 但我认为这只会使事情变得模糊）。可能还有很多其他方面可以大大改进，但我认为逻辑已经到位。
再多说几句：实现假定模式格式正确（没有不匹配的左括号或右括号）。另外，我从这个答案中获取了数组交集代码，因为它很紧凑 - 如果有必要，你当然可以提高它的效率。
不管这些实现细节如何，我想我也可以回答你的复杂性问题：外循环同时遍历两个字符串，一次遍历一个字符。这就是线性复杂度。循环中的所有内容都可以在恒定时间内完成，除了字符类测试。如果一个字符是字符类而另一个不是，则需要线性时间（以类的大小为参数）来检查字符是否在类中。但这并不能使它成为二次方，因为类中的每个字符都意味着外循环的迭代次数减少了一次。所以这仍然是线性的。因此，最昂贵的事情是两个字符类的交集。这可能比线性时间更复杂，但最糟糕的是O(N log N)：毕竟，您可以对两个字符类进行排序，然后在线性时间内找到一个交集。我认为你甚至可以通过将字符类中的字符散列到它们的 Unicode 代码点（.charCodeAt(0)在 JS 中）或其他数字来获得整体线性时间复杂度——并且可以在线性时间内找到散列集中的交集。所以，如果你真的想，我认为你应该能够开始O(N)。
什么是N？上限是两种模式的长度之和，但在大多数情况下它实际上会更短（取决于两种模式的前缀和后缀的长度）。
请指出我的算法丢失的任何边缘情况。我也很高兴建议的改进，如果它们改进或至少不降低代码的清晰度。
这是 JSBin 的现场演示（感谢 chakrit 将其粘贴在那里）。
编辑：正如丹尼尔指出的那样，我的算法错过了一个概念性的边缘情况。如果（在消除开头和结尾之前或之后）一个字符串包含 no*而另一个包含 no，则在某些情况下，两者仍然会发生冲突。不幸的是，我现在没有时间调整我的代码片段以适应该问题，但我可以概述如何解决它。
消除字符串的两端后，如果两个字符串都为空或都包含至少*，它们将始终匹配（通过*完全消除后可能的 - 分布来查看这一点）。唯一不重要的情况是一个字符串仍然包含*，但另一个不包含（无论是否为空）。我们现在需要做的是再次从左到右走两个字符串。让我称包含*A 的字符串和不包含*B的字符串。
我们从左到右遍历 A，跳过所有*（只关注?、字符类和文字字符）。对于每个相关的标记，我们从左到右检查它是否可以在 B 中匹配（在第一次出现时停止）并将 B 光标推进到该位置。如果我们在 A 中找到一个在 B 中找不到的标记，它们就不匹配。如果我们设法为 A 中的每个标记找到匹配项，它们确实匹配。这样，我们仍然使用线性时间，因为不涉及回溯。这里有两个例子。这两个应该匹配：
A: *a*[bc]*?*d* --- B: db?bdfdc
^ ^
A: *a*[bc]*?*d* --- B: db?bdfdc
^ ^
A: *a*[bc]*?*d* --- B: db?bdfdc
^ ^
A: *a*[bc]*?*d* --- B: db?bdfdc
^ ^
这两个不应该匹配：
A: *a*[bc]*?*d* --- B: dbabdfc
^ ^
A: *a*[bc]*?*d* --- B: dbabdfc
^ ^
A: *a*[bc]*?*d* --- B: dbabdfc
^ ^
A: *a*[bc]*?*d* --- B: dbabdfc
!
它失败了，因为在?second 之前不可能匹配d，之后 B 中没有进一步d的内容来容纳dA中的最后一个。
如果我花时间将字符串正确解析为令牌对象，这可能很容易添加到我当前的实现中。但是现在，我不得不再次麻烦地解析这些字符类。我希望这个添加的书面大纲是足够的帮助。
PS：当然，我的实现也没有考虑转义元字符，并且可能会阻塞*内部字符类。
