使用 KMP 算法处理字符串匹配中的通配符“*"运算符? [英] Handling wildcard '*' operator in string matching using KMP-Algorithm?

问题描述

如果要匹配的模式中包含通配符*，比如AB*C，出现的就是文本，<代码>ABEFGCS(这里*消耗字符EFG)使用KMP算法?

How should I handle the case when the pattern to be matched contains the wildcard character, *, such as AB*C, which is present is the text, ABEFGCS (here * consumes characters EFG) using the KMP-Algorithm ?

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

What modification in the algorithm can solve this problem ?

推荐答案

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

Actually I got it, leaving answer for reference, we can simply break the string about the wildcard operator, apply KMP on each part, and check whether each part is a sub-string or not, also, whether the parts are contiguous or not can be checked in linear time, hence the overall time complexity is still linear.

这篇关于使用 KMP 算法处理字符串匹配中的通配符“*"运算符?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！