使用DOS通配符强制执行字符串的最快方法

Question

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

直截了当的方法是测试,a*, b*, c*...直到找到第一个字母,然后重复.我能想到的一些优化:

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

Answer 1

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

\n\n

\n
• Check Z*whereZ代表k问号，从 0 开始，然后是 1，然后每次检查时将问号数量加倍，直到没有匹配项出现。n必须在k / 2和 之间k
\n
• k使用与二分搜索相同的模式变化来查找确切的长度。
\n

\n\n

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

\n\n

更新

\n\n

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

\n\n

例子：

\n\n

\n ..X。..XX（为便于阅读而添加空格）\n\n + 符号可能是 X\n - 符号不是 X\n X 符号是 X\n\n *X* => MATCH ++++ ++++\ n*X* ???? => 匹配 ++++ ++++\n *X*?? ???? => 不匹配 --++ ++++\n ??X? ???? => 匹配 --X+ ++++\n ??XX ???? => 不匹配 --X- ++++\n ??X? *X*？？=> 不匹配 --X- --++\n ??X? ？？X？=> 匹配 --X- --X+\n ??X? ??XX => 匹配 --X- --XX\n

\n\n

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

\n\n

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

\n\n

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

\n