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

>检查Z *,其中Z表示从0开始的k个问号,然后是1,然后每次检查将问号的数量加倍,直到不匹配为止. n必须在k / 2和k之间
>使用相同的模式更改k,以与二分查找相同的方式查找确切的长度.

知道确切的长度可能有助于在空间域中执行一种除法.

UPDATE

如果知道长度,则可以使用相同的模式正确定位符号.

例：

    ..X. ..XX (spaces added for readability)

                              + symbol may be X
                              - symbol is not X
                              X symbol is X

    *X*         => MATCH      ++++ ++++
    *X*   ????  => MATCH      ++++ ++++
    *X*?? ????  => NO MATCH   --++ ++++
    ??X?  ????  => MATCH      --X+ ++++
    ??XX  ????  => NO MATCH   --X- ++++
    ??X?  *X*?? => NO MATCH   --X- --++
    ??X?  ??X?  => MATCH      --X- --X+
    ??X?  ??XX  => MATCH      --X- --XX

对于字符串长度n和字母大小m,这将需要大约O(log2(n))来查找字符串的长度,大约O(n?log2(n))以正确放置n个符号,并且O(m)来查找使用的符号 – 总计得到的结果为O(n?log2(n)m).

我可以想象通过合并几个步骤可以加快速度 – 可以在确定字符串长度的同时测试用过的符号,或者在字符串的第一个和第二个半部分中同时定位两个(甚至更多？)符号.如果检查失败,这将需要单独重新检查合并的步骤,以确定哪个检查faild.但只要合并检查成功,您就可以获得两者的信息.

也许我会在明天计算一下,看看它是否会真正加快速度.