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

Question

当要匹配的模式包含通配符时，我应该如何处理使用 KMP-Algorithm的通配符*，例如AB*C，存在的是文本ABEFGCS（此处使用*字符EFG）？

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

Answer 1

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