我正在尝试确定为特定用例实施模式匹配算法的最佳方法。我将对我正在尝试做的事情进行一些抽象。
我希望我的算法能够搜索一系列字符，并找到与特定模式的第一个匹配项。有一些微妙之处。首先，字符可以以任何顺序出现。此外，该模式可能包含通配符，并且可能有多种类型的通配符。
例如，假设我们有一个模式？A？G？G，其中？表示前面的字符是通配符。因此，该模式正在寻找任何字符和两个重复字符的第一个匹配项，以任何顺序出现。然后我们可以有一个序列“ABCDEFF”。作为树进行深度优先搜索，该算法将找到匹配的 AFF。请注意，对于序列 FABCDEF，我们还会找到匹配项 AFF，因为顺序并不重要。
我估计这会有大约 O(n m!) 的运行时间，其中 n 是模式长度，m 是序列长度。显然，这对于搜索长序列来说并不理想。我只是想知道是否有一种聪明或最好的方法来实现这个，或者是否有任何类型的模拟技术等可以提高算法的速度。