带通配符*的字符串匹配次数统计函数原理及性能问题咨询

一、函数的匹配逻辑&重叠匹配处理规则 #

这段递归代码的核心逻辑是枚举所有通配符*的可能匹配长度，统计所有符合条件的拆分方式总数，对重叠匹配的处理完全符合题设要求：

• 终止条件：当两个字符串同时遍历到末尾时，说明当前拆分方式匹配成功，返回1计数
• 当模式串当前字符为*时：
  枚举这个*匹配0到任意长度的主串剩余内容，把所有拆分方式下后续的匹配计数全部累加，这也是重叠匹配会被分别计数的核心原因——只要*匹配的长度不同，哪怕后续匹配的字符有重叠，不同的拆分方式都会被单独统计
• 当两个字符串当前字符相等时，同时后移一位继续匹配
• 当前字符不相等时，当前路径匹配失败，返回0

我们可以用你给出的第二个示例验证逻辑：主串abc、模式串a**

1. 先匹配固定字符a，主串剩余bc，模式串剩余**
2. 处理第一个*：枚举匹配长度0、1、2：
   • 匹配长度0：主串剩余bc，模式串剩余*，第二个*匹配全部bc，计数+1
   • 匹配长度1：主串剩余c，模式串剩余*，第二个*匹配全部c，计数+1
   • 匹配长度2：主串剩余空，模式串剩余*，第二个*匹配空，计数+1
3. 总计数为3，和示例完全一致。

二、组合爆炸测试用例的运行结果 #

这段代码没有做任何记忆化优化，所有递归状态不会被缓存，会产生大量重复计算，时间复杂度是指数级的：假设主串长度为n，模式串中*的数量为k，时间复杂度大概是O(n^k)。
你给出的测试用例：20个x加末尾的a，模式串是*x*x*x*x*a（共5个*和4个x、1个a），运行时会出现两个问题：

• 递归调用次数爆炸，运行时间会非常长，远高于线性/动态规划实现的解法
• 递归深度过高的情况下，还可能直接触发栈溢出，程序崩溃退出，完全无法得到结果。

内容的提问来源于stack exchange，提问作者Infinite_improbability