现在见证这个全副武装和作战站的火力！

• （我在这个答案上下了太多功夫，脑子都坏了;应该有一个徽章。）*

为了确定两个模式是否相交，我创建了一个递归回溯解析器--当遇到***Kleene star***时，会创建一个新的堆栈，这样如果将来失败，所有内容都会回滚，并且***star***会消耗下一个字符。
你可以查看这个答案的历史，以确定这一切是如何得出的，以及为什么它是必要的，但基本上，它是不够的，以确定一个交叉点，向前看只有一个令牌，这是我之前所做的。
这就是打破旧答案[abcd]d => *d的情况。***set***匹配***星星***之后的d，因此左侧仍有令牌剩余，而右侧则是完整的。然而，这两个图案在ad、bd、cd和dd上相交，因此需要固定。我的 almost O（N）答案被抛出了。

Lexer

词法分析过程很简单，除了处理转义字符和删除多余的星号。令牌被分解为集*、星、***野生字符（？）和***字符。这与我以前的版本不同，在以前的版本中，一个令牌是一个字符串，而不是一个字符。随着越来越多的案例出现，将字符串作为令牌是一种阻碍而不是优势。

解析器

解析器的大多数功能都很简单。给定左侧类型的开关调用一个函数，该函数是一个开关，该开关确定适当的函数以将其与右侧的类型进行比较。比较的结果将两个开关向上冒泡到原始被调用方，通常是解析器的主循环。

解析星星

简单性以***星星***结束。当它遇到它接管一切。首先，它将自己一方的下一个令牌与另一方的令牌进行比较，推进另一方，直到找到匹配。
一旦找到匹配，它就会检查是否所有内容都匹配到两个模式的末尾。如果是这样，那么模式就相交了。否则，它将另一方的下一个令牌从与之进行比较的原始令牌前进，并重复该过程。
当遇到两个***anys***时，则从彼此的下一个令牌开始进入各自的替代分支。

function intersects(left, right) {
    var lt, rt,
        result = new CompareResult(null, null, true);

    lt = (!left || left instanceof Token) ? left : tokenize(left);
    rt = (!right || right instanceof Token) ? right : tokenize(right);

    while (result.isGood && (lt || rt)) {
        result = tokensCompare(lt, rt);

        lt = result.leftNext;
        rt = result.rightNext;
    }

    return result;
}

function tokensCompare(lt, rt) {
    if (!lt && rt) return tokensCompare(rt, lt).swapTokens();

    switch (lt.type) {
        case TokenType.Char: return charCompare(lt, rt);
        case TokenType.Single: return singleCompare(lt, rt);
        case TokenType.Set: return setCompare(lt, rt);
        case TokenType.AnyString: return anyCompare(lt, rt);
    }
}

function anyCompare(tAny, tOther) {
    if (!tOther) return new CompareResult(tAny.next, null);

    var result = CompareResult.BadResult;

    while (tOther && !result.isGood) {
        while (tOther && !result.isGood) {
            switch (tOther.type) {
                case TokenType.Char: result = charCompare(tOther, tAny.next).swapTokens(); break;
                case TokenType.Single: result = singleCompare(tOther, tAny.next).swapTokens(); break;
                case TokenType.Set: result = setCompare(tOther, tAny.next).swapTokens(); break;
                case TokenType.AnyString:
                    // the anyCompare from the intersects will take over the processing.
                    result = intersects(tAny, tOther.next);
                    if (result.isGood) return result;
                    return intersects(tOther, tAny.next).swapTokens();
            }

            if (!result.isGood) tOther = tOther.next;
        }

        if (result.isGood) {
            // we've found a starting point, but now we want to make sure this will always work.
            result = intersects(result.leftNext, result.rightNext);
            if (!result.isGood) tOther = tOther.next;
        }
    }

    // If we never got a good result that means we've eaten everything.
    if (!result.isGood) result = new CompareResult(tAny.next, null, true);

    return result;
}

function charCompare(tChar, tOther) {
    if (!tOther) return CompareResult.BadResult;

    switch (tOther.type) {
        case TokenType.Char: return charCharCompare(tChar, tOther); 
        case TokenType.Single: return new CompareResult(tChar.next, tOther.next);
        case TokenType.Set: return setCharCompare(tOther, tChar).swapTokens(); 
        case TokenType.AnyString: return anyCompare(tOther, tChar).swapTokens();
    }
}

function singleCompare(tSingle, tOther) {
    if (!tOther) return CompareResult.BadResult;

    switch (tOther.type) {
        case TokenType.Char: return new CompareResult(tSingle.next, tOther.next);
        case TokenType.Single: return new CompareResult(tSingle.next, tOther.next);
        case TokenType.Set: return new CompareResult(tSingle.next, tOther.next);
        case TokenType.AnyString: return anyCompare(tOther, tSingle).swapTokens();
    }
}
function setCompare(tSet, tOther) {
    if (!tOther) return CompareResult.BadResult;

    switch (tOther.type) {
        case TokenType.Char: return setCharCompare(tSet, tOther);
        case TokenType.Single: return new CompareResult(tSet.next, tOther.next);
        case TokenType.Set: return setSetCompare(tSet, tOther);
        case TokenType.AnyString: return anyCompare(tOther, tSet).swapTokens();
    }
}

function anySingleCompare(tAny, tSingle) {
    var nextResult = (tAny.next) ? singleCompare(tSingle, tAny.next).swapTokens() :
        new CompareResult(tAny, tSingle.next);
    return (nextResult.isGood) ? nextResult: new CompareResult(tAny, tSingle.next);
}

function anyCharCompare(tAny, tChar) {
    var nextResult = (tAny.next) ? charCompare(tChar, tAny.next).swapTokens() :
        new CompareResult(tAny, tChar.next);

    return (nextResult.isGood) ? nextResult : new CompareResult(tAny, tChar.next);
}

function charCharCompare(litA, litB) {
    return (litA.val === litB.val) ?
        new CompareResult(litA.next, litB.next) : CompareResult.BadResult;
}

function setCharCompare(tSet, tChar) {
    return (tSet.val.indexOf(tChar.val) > -1) ?
        new CompareResult(tSet.next, tChar.next) : CompareResult.BadResult;
}

function setSetCompare(tSetA, tSetB) {
    var setA = tSetA.val,
        setB = tSetB.val;

    for (var i = 0, il = setA.length; i < il; i++) {
        if (setB.indexOf(setA.charAt(i)) > -1) return new CompareResult(tSetA.next, tSetB.next);
    }
    return CompareResult.BadResult;
}

jsFiddle

时间复杂度

任何带有“递归回溯”的东西都至少是O（N2）。

可维护性和可读性

我故意打破了任何分支到有自己的功能与一个单一的开关。当一个字符串就足够时，我辅助地使用命名常量。这样做会使代码更长、更冗长，但我认为这样更容易理解。

测试

您可以在Fiddle中查看所有测试。您可以查看Fiddle输出中的注解以了解它们的用途。每种标记类型都针对每种标记类型进行了测试，但我还没有在一个测试中尝试所有可能的比较。我也想出了一些随机的坚韧的，像下面的一个。
abc[def]?fghi?*nop*[tuv]uv[wxy]?yz => a?[cde]defg*?ilmn[opq]*tu*[xyz]*
我在**jsFiddle**上添加了一个接口，如果有人想自己测试一下。一旦我添加了递归，日志记录就被破坏了。
我认为我没有尝试足够的负面测试，尤其是我创建的最后一个版本。

优化

目前的解决方案是蛮力的，但足以处理任何情况。我想在某个时候回到这一点，通过一些简单的优化来改善时间复杂度。
在开始时进行检查以减少比较可能会增加某些常见情况的处理时间。例如，如果一个模式以***星***开始，一个以1结束，那么我们已经知道它们将相交。我也可以检查所有的字符从开始和结束的模式，并删除他们，如果匹配的两个模式。这样，它们就被排除在任何未来的递归之外。

致谢

我最初使用**@m.buettner的**tests来测试我的代码，然后我想出自己的代码。我还浏览了他的代码，以帮助我更好地理解这个问题。

使用您非常精简的模式语言，您的问题和jpmc 26的注解中的pastebin链接几乎都在那里：主要的问题是，输入字符串的左、右结尾是否匹配。如果它们包含，并且都包含至少一个*，则字符串匹配（因为您总是可以将其他字符串中间的文字文本与该星星匹配）。有一个特殊情况：如果其中只有一个是空的（在删除前缀和后缀之后），如果另一个完全由* s组成，它们仍然可以匹配。
当然，在检查字符串的结尾是否匹配时，还需要考虑单字符通配符?和字符类。单字符通配符很简单：它不会失败，因为它总是匹配其他字符。如果它是一个字符类，而另一个只是一个字符，则需要检查该字符是否在该类中。如果它们都是类，则需要检查类的交集（简单的集合交集）。
下面是JavaScript中的所有内容（查看代码注解，看看上面概述的算法是如何Map到代码的）：

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来减轻-但我认为这只会使事情变得模糊）。可能还有很多其他的部分可以得到很大的改进，但我认为逻辑已经到位了。
再补充几句：该实现假设模式格式良好（没有不匹配的左括号或右括号）。此外，我从this answer中获取了数组交集代码，因为它很紧凑--如果有必要，当然可以提高效率。
不管这些实现细节如何，我想我也可以回答你的复杂性问题：外部循环同时遍历两个字符串，一次遍历一个字符。这就是线性复杂性。除了字符类测试之外，循环中的所有事情都可以在恒定时间内完成。如果一个字符是字符类而另一个不是，则需要线性时间（类的大小是参数）来检查字符是否在类中。但这并不意味着它是二次的，因为类中的每个字符意味着外部循环的迭代次数减少了一次。所以这仍然是线性的。因此，最昂贵的事情是两个字符类的交集。这可能比线性时间更复杂，但最糟糕的情况是O(N log N)：毕竟，你可以只对两个字符类进行排序，然后在线性时间内找到一个交集。我认为你甚至可以通过将字符类中的字符散列到它们的Unicode代码点（JS中的.charCodeAt(0)）或其他一些数字来获得整体线性时间复杂度-在散列集中找到交集是可能的。所以，如果你真的想，我认为你应该能够得到O(N)。
什么是N？上限是两种模式的长度之和，但在大多数情况下，它实际上会更小（取决于两种模式的前缀和后缀的长度）。
请指出我的算法遗漏的任何边缘情况。我也很高兴建议的改进，如果他们改善或至少不降低代码的清晰度。
Here is a live demo on JSBin（感谢chakrit将其粘贴在那里）。

**编辑：**正如丹尼尔指出的，我的算法错过了一个概念上的边缘情况。如果（在消除开头和结尾之前或之后）一个字符串不包含*，而另一个字符串包含*，则在某些情况下，这两个字符串仍然冲突。不幸的是，我现在没有时间调整代码片段来适应这个问题，但我可以概述如何解决它。

在消除字符串的两端之后，如果两个字符串都是空的或者都至少包含*，它们将始终匹配（在完全消除之后查看可能的*-分布）。唯一不平凡的情况是一个字符串仍然包含*，但另一个不包含（无论是否为空）。我们现在需要做的是再次从左到右遍历两个字符串。让我将包含*的字符串称为A，将不包含x1m13 n1 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
             !

它失败了，因为?不可能在第二个d之前匹配，之后B中没有更多的d来容纳A中的最后一个d。
如果我花时间将字符串正确地解析为令牌对象，那么将其添加到我当前的实现中可能很容易。但是现在，我不得不再次经历解析这些字符类的麻烦。我希望这份书面大纲的补充是足够的帮助。
PS：当然，我的实现也没有考虑转义元字符，并且可能会在字符类中被*卡住。

这些特殊模式的功能远不如完整的正则表达式强大，但我会指出，即使使用一般的正则表达式，也可以做你想做的事情。这些必须是“真”正则表达式，即那些只使用Kleene星星，交替（the|操作），以及与任何固定字母加上空字符串和空集的串联。当然，你也可以在这些操作中使用任何语法糖：一个或多个（+）、可选（？）。字符集只是一种特殊的交替[a-c] == a| B| c.第一次会议
该算法原理简单：使用标准构造将每个正则表达式转换为DFA：汤普森紧随其后。然后使用叉积构造来计算两个原件的交集DFA。最后，检查这个交集DFA，以确定它是否至少接受一个字符串。这只是从开始状态开始的dfs，以查看是否可以达到接受状态。
如果你不熟悉这些算法，很容易找到互联网参考。
如果交集DFA接受了至少一个字符串，则原始正则表达式之间存在匹配，并且dfs发现的路径给出了满足两者的字符串。否则没有匹配。

问得好！
这里主要的复杂性是处理字符类（[...]）。我的方法是用一个正则表达式来替换每一个，该正则表达式查找 * either * 指定字符中的一个（或?）* 或 * 至少包含一个指定字符的另一个字符类。所以对于[xyz]，这将是：([xyz?]|\[[^\]]*[xyz].*?\])-见下文：

然后对于“前缀”（第一个*之前的所有内容），将^放在开头，或者对于“后缀”（最后一个*之后的所有内容），将$放在结尾。
更多详情：-
1.还需要将?的所有示例替换为(\[.*?\]|[^\\]])，以使其匹配字符类或单个字符（不包括左方括号）。
1.还需要替换不在字符类中且不是?的每个字符，以使其匹配相同的字符?或包含该字符的字符类。例如，a将变为([a?]|\[[^\]]*a.*?\])。（有点罗嗦，但事实证明是必要的-见下面的评论）。
1.测试应按以下方式进行：针对前缀#2测试 * 前缀#1转换为regex*，然后针对前缀#1测试 * 前缀#2转换为regex*。如果任一匹配，则前缀可以被称为“相交”。
1.对后缀重复步骤（3.）：对于正结果，* 前缀和后缀必须相交。

**EDIT：**除了上述情况外，还有一种特殊情况，即其中一个模式至少包含一个*，但另一个模式不包含。在这种情况下，带有*的整个模式应该转换为正则表达式：*应该匹配任何东西，但附带条件是它只包括 * 整个 * 字符类。这可以通过将*的所有示例替换为(\[.*?\]|[^\\]])来完成。

为了避免这个答案变得冗长，我不会发布完整的代码，但这里有一个单元测试的工作演示：http://jsfiddle.net/mb3Hn/4/

**编辑#2 -已知的不完整性：**在当前形式下，演示不适合转义字符（例如：\[）。这不是一个很好的借口，但我只是在当天晚些时候才注意到这些-他们没有在问题中提到，只有link。为了处理它们，需要增加一点正则表达式的复杂性，例如：检查[之前是否存在反斜杠。使用negative lookbehind这应该是相当轻松的，但不幸的是JavaScript不支持它。有一些变通方法，比如用负前瞻来反转字符串和正则表达式，但我不热衷于用这种额外的复杂性来降低代码的可读性，也不确定它对OP有多重要，所以将其作为“读者的练习”。回想起来，也许应该选择一种具有更全面的正则表达式支持的语言！

使用greenery确定一个正则表达式是否匹配另一个正则表达式的子集：
首先，pip3 install https://github.com/ferno/greenery/archive/master.zip。
然后：

from greenery.lego import parse as p
a_z = p("[a-z]")
b_x = p("[b-x]")
assert a_z | b_x == a_z
m_n = p("m|n")
zero_nine = p("[0-9]")
assert not m_n | zero_nine == m_n

我写了这个Go项目：glob-intersection，主要感谢这里的讨论，早在2017年。
它是正则表达式风格的globs，所以必须使用.*而不是*，但是@chakrit在他们的原始帖子中给出的所有示例都应该可以工作。