有人问我一个面试问题：写一个函数match(s, t)来决定字符串s是否是另一个字符串t的广义子字符串。更具体地说，match应该返回True，当且仅当删除t中的一些字符可以使其与s相等时。例如，match("abc", "abbbc")为True，因为我们可以删除t中额外的两个b。
当然，面试官期待着某种递归的解决方案，但我很有冒险精神，写了
def match(s, t):
return re.search('.*?'.join(s), t) is not None
这似乎满足了所有的测试用例，但后来我开始怀疑是否存在任何可以占用此操作的对抗性输入(并可能使我们的服务容易受到DoS攻击(。请参阅这篇伟大的文章进行深入的讨论，但作为一个快速的例子，请尝试
re.match("a?"*29+"a"*29, "a"*29)
在找到匹配项之前需要几秒钟的时间。原因是re实现了一个回溯正则表达式引擎：
考虑正则表达式anan。当a？被选择为不匹配任何字母，留下整个字符串由an匹配。回溯正则表达式实现实现零还是一？先尝试1，然后再尝试0。有n个这样的选择要做，总共有2n的可能性。只有最后一种可能性——为所有选择零--将导致一场比赛。因此，回溯方法需要O(2n(时间，因此它不会扩展到n=25以上。
回到面试问题，从技术上讲，'.*?'.join(s)至少给了我们len(s) - 1的选择，这意味着可能会有一些类似于上面的"a?"*29+"a"*29和"a"*29的对抗性输入，但经过一番尝试和错误，我没能找到它们。
问题：s和t是什么让match慢得离谱？
懒惰的量词通常对性能很好，但AFAIK它们不能阻止病理性强调行为。
当regexp的开头与文本的开头匹配时尤其如此，但匹配是早期的，并且在需要大量回溯的文本末尾将失败；"修复"；regexp开头的糟糕的早期懒惰匹配。
在您的情况下，这里有一个需要指数级步骤的病理输入示例：
# This should take at least few minutes to compute
n = 12
match('ab'*(n+1), 'abbbbb'*n+'a')
以下是基于n:的值所需的步骤数和Pythonmatch时间
n | steps | time
1 | 44 | 2.4 µs
2 | 374 | 6.4 µs
3 | 2621 | 22.1 µs
4 | 18353 | 131.3 µs
5 | 126211 | 925.8 µs
6 | - | 6.2 ms
7 | - | 42.2 ms
8 | - | 288.7 ms
9 | - | 1.97 s
您可以在这个伟大的网站上理解和分析由此产生的regexp匹配行为(在这种情况下更具体地说是回溯(。
您的解决方案由于回溯而受到影响，这就是为什么接受的答案能够提供输入，从而大大降低速度。
这里有一个regex解决方案，它与我之前的答案非常相似，而且似乎也避免了困扰您当前解决方案的问题。
def match(s, t):
return re.search("".join(f'[^{re.escape(c)}]*{re.escape(c)}' for c in s), t) is not None
上一个答案
这并不能直接回答你的问题，但
面试官肯定在期待某种递归解决方案。。。
我不这么认为。像这样的东西也可以工作
def match(s, t):
i = -1
return all ((i := t.find(c, i + 1)) != -1 for c in s)
我只是想提供一种替代解决方案，它不需要递归或正则表达式，因此不会导致您提到的漏洞。