已经在其中包含通配符的字符串上的模式匹配

Question

我有一个场景,我想在其中已经有通配符的字符串上使用通配模式进行搜索.用我的话来说,我会说这是一种双向模式匹配要求.

输入和模式字符串可以包含以下任一/两个通配符 - ？表示单个字符,%表示零个或多个字符.假设这些是输入和模式字符串中允许的唯一2个通配符.

例如:

bool IsMatch(字符串输入,字符串模式)//如果输入字符串与模式匹配,则应返回True,否则返回False.

IsMatch("XYZ%","？Y%")//应该返回True

IsMatch("YY？","？Y%")//应该返回True - 输入字符串中的最后一个字符需要单个字符,其中模式匹配Y之后的零个或多个字符(这意味着它包含单个字符匹配为好)

IsMatch("X123","？Y%")//应该返回False - 在模式期望的输入字符串中缺少Y

IsMatch("？Y%","？Y%")//应返回True

IsMatch("%","？Y%")//应返回True - 输入字符串具有表示零个或多个字符的通配符%,并且还可以包含任何字符.在某种程度上,它作为一种模式,本身代表任何大小的任何东西.

我能够找到只讨论在非通配字符串上执行通配模式匹配的文章(例如:Regex).我正在寻找关于算法的指针/想法,因为我很难想出一种可以做这种匹配的算法,因为我开始放下它.感谢您的意见.

Answer 1

正如我在针对最常见情况的评论中所写的那样，您必须创建两个表达式的最小确定性有限自动机并比较这两个自动机。话虽如此，你的问题可能有一个暴力/穷人的解决方案。

根据您的示例，听起来您有兴趣查看其中一个输入/模式是否与另一个输入/模式生成的所有字符串匹配。

IsMatch("XYZ%", "?Y%") // returns true because ?Y% matches a superset of strings matched by "XYZ%"
IsMatch("%", "?Y%") // returns true because "%" matches a superset of "?Y%"

您可以检查是否确实匹配只要input 生成的字符串子集pattern

• 你真的可以将自己限制在%和？指定的运算符
• 您的输入/模式字符串相当短 - 更具体地说，输入或模式中 % 的出现次数少于 20 左右。

基本思想是您生成一个代表性字符串列表，input并使用您最喜欢的正则表达式引擎将每个字符串与模式进行匹配。如果所有代表都匹配 -input匹配 的子集pattern。该算法IsSubset可以描述如下

let c = some character not in `pattern` (lexically speaking)
let searchString = replace all occurences of '?' in input with c
add searchString to setOfSearchStrings
foreach occurence of '%' in input
    foreach str in setOfSearchStrings
        replace str with two strings - {str with c in place of '%', str without the '%'}

foreach str in setOfSearchStrings
   if str doesn't "regex" match with pattern 
       return false

return true

例如，如果输入是 ?X%YZ% 并且pattern不包含字符 A，则生成的列表将为
AXYZ
AXYZA
AXAYZ
AXAYZA

很容易看出此列表中的字符串数量为 2^n，其中 n 是输入中“%”的数量。

此外，交换参数的顺序并以相反的方式找出关系也很容易。所以实际上你的

IsMatch(input,pattern) = IsSubset(input,pattern) || IsSubset(pattern,input)