algorithm - 使用 KMP 算法在字符串匹配中处理通配符“*”运算符？

Question

当要匹配的模式包含通配符时，我应该如何使用KMP *- Algorithm处理这种情况？AB*CABEFGCS*EFG

算法中的哪些修改可以解决这个问题？

Answer 1

其实我明白了，留下答案供参考，我们可以简单地打破关于通配符的字符串，对每个部分应用KMP，并检查每个部分是否是一个子字符串，并且这些部分是否连续可以以线性时间检查，因此总体时间复杂度仍然是线性的。