6

这个问题类似于盲目的 SQL 注入。目标是确定字符串的确切值，您唯一能做的测试是查看您指定的 DOS 样式通配符（？= 任意字符，* = 任意数量的任意字符）是否与字符串匹配。（所以实际上你只能访问一个bool DoesWildcardMatch(string wildcard)函数）。

直接的方法是进行测试，a*, b*, c*...直到找到第一个字母，然后重复。我能想到的一些优化：

  • 搜索*a*, *b*etc. 以确定字符集
  • 当*x*找到匹配项时，执行 divide-et-impera ( *a*x*, *b*x*, ...)
4

4 回答 4

2

至于分权，请务必跟踪您知道不存在的价值。我也不会使用a, b, c，而是使用频率顺序。某种马尔可夫链可能会使其更快。

需要注意的一件事是，您不能假设给定的文字将始终与输入中的相同位置匹配。这对于在最后删除通配符特别感兴趣。

c a b a
--------
* a *     match
  * b*a*  woops!
于 2009-05-14T19:34:17.843 回答
2

第一个想法。您可以确定n字符串的长度O(log2(n))。

  • 检查Z*whereZ表示k问号，从 0 开始，然后是 1，然后每次检查都将问号的数量加倍，直到不匹配。n必须在k / 2和之间k
  • k使用与二进制搜索相同的方式更改相同的模式找到确切的长度。

知道确切的长度可能有助于在空间域中执行一种分而治之的方法。

更新

如果您知道长度，则可以使用相同的模式来正确定位符号。

例子：

    ..X。..XX（为便于阅读添加了空格）

                              + 符号可能是 X
                              - 符号不是 X
                              X 符号是 X

    *X* => 匹配 ++++ ++++
    *X* ？？？？=> 匹配 ++++ ++++
    *X*？？？？？=> 不匹配 --++ ++++
    ？？X？？？？=> 匹配 --X+ ++++
    ??XX???? => 不匹配 --X- ++++
    ？？X？*X*？？=> 不匹配 --X- --++
    ？？X？？？X？=> 匹配 --X- --X+
    ？？X？??XX => 匹配 --X- --XX

对于字符串长度n和字母大小，m这将需要O(log2(n))找到字符串的长度，O(n • log2(n))正确放置n符号，并O(m)找到使用的符号 - 将所有符号加在一起产生O(n • log2(n) + m)。

我可以想象，可以通过合并几个步骤来加快速度 - 可能在确定字符串长度的同时测试使用的符号，或者同时在字符串的前半部分和后半部分定位两个（甚至更多？）符号。如果检查失败，这将需要单独重新检查合并的步骤，以确定哪个检查失败。但只要合并检查成功，您就可以获得两者的信息。

也许我明天会计算一下，看看它是否真的会加快速度。

于 2009-05-14T19:39:04.603 回答
1

如果具体数量？有效，你也可以检查“？”，“？？”，“？？？” 等等来获取字符串的长度，但我怀疑这会有所帮助，因为您还可以在每轮之后只进行一次额外检查而无需任何通配符来检查您是否获得了正确的长度。

我认为之前带有字符集检查的分割方法几乎是最佳的，还有一些额外的细节，例如如果你匹配*a*b*，你应该*ab*在之后检查是否有字母，当然如上所述，检查*ab和“ab “在此之后知道你是在右侧完成还是完全完成。

于 2009-05-14T19:20:03.557 回答
0

为什么不将 DOS 风格的通配符字符串转换为正则表达式？例如：

？一种*

变成：

。一种。*

然后只需执行一个简单的正则表达式匹配，将其与您的测试字符串进行比较。

于 2009-05-14T19:23:20.680 回答