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

（我在这个答案上做得太多了，我的脑袋坏了；应该有一个徽章。）

为了确定两个模式是否相交，我创建了一个递归的回溯解析器-当遇到 Kleene星时
，会创建一个新的堆栈，以便如果将来失败，则所有内容都会回滚，并且该 星 消耗下一个字符。

您可以查看此答案的历史记录，以确定如何得出所有结果以及为什么这样做的必要性，但基本上，仅向前看一个标记就不足以确定一个交叉点，而这正是我之前所做的。

这是打破旧答案[abcd]d=>的情况*d。该 集合 与
stard之后的匹配，因此左侧将仍然保留令牌，而右侧将是完整的。然而，这些图案的两个相交上，，和，因此需要加以固定。我 几乎是
O（N）的答案被抛出了。 __ad``bd``cd``dd __

Lexer

词法化过程很简单，除了过程是转义字符并删除多余的 星星 。令牌分为 集合 ， 星号 ， 通配符（？）
和 character
。这与我以前的版本不同，在我以前的版本中，一个标记是一个字符串而不是一个字符。随着越来越多的案例出现，使用字符串作为令牌更多的是障碍而不是优势。

解析器

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

解析星星

简单以 星星 结束。遇到这种情况时，它将接管一切。首先，它将对方的下一个令牌与对方的下一个令牌进行比较，将对方推进，直到找到匹配为止。

找到匹配项后，它将检查所有模式是否都匹配到两个模式的末尾。如果是这样，则图案相交。否则，它将从与之比较的原始令牌中移出另一方的下一个令牌，并重复该过程。

当遇到两个 任意 一个时，则从彼此的下一个令牌开始进入其自己的替代分支。

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（N 2）。

可维护性和可读性

我故意用单个开关将所有分支分解成自己的功能。当一个字符串就足够时，我通常使用命名常量。这样做使代码更长，更冗长，但是我认为它使遵循起来更加容易。

测验

您可以在小提琴中查看所有测试。您可以在Fiddle输出中查看注释，以了解其目的。每种令牌类型都针对每种令牌类型进行了测试，但是我还没有做过一次测试中所有可能比较的尝试。我还想出了一些随机的艰难难题，例如下面的难题。

abc[def]?fghi?*nop*[tuv]uv[wxy]?yz => a?[cde]defg*?ilmn[opq]*tu*[xyz]*

如果有人想自己测试一下，我在 jsFiddle
上添加了一个接口。一旦添加递归，日志记录就会中断。

我认为我没有进行足够的负面测试，尤其是在我创建的最后一个版本中。

优化

当前，解决方案是蛮力的，但足以应付任何情况。我想回到这一点，通过一些简单的优化来改善时间复杂度。

开始时进行检查以减少比较，对于某些常见情况可能会增加处理时间。例如，如果一种模式以 星形 开始，而一种模式以 星形
结束，那么我们已经知道它们将相交。我还可以检查模式开头和结尾的所有字符，如果两个模式都匹配，则将其删除。这样，它们便不再包含在将来的递归中。

致谢

在提出自己的代码之前，我最初使用 @ m.buettner的 测试来测试代码。我也浏览了他的代码，以帮助我更好地理解问题。