吴炳璋算法

一个基于递归的二分查找算法，由于其证明极其繁琐，故直接给出伪代码：

//STR为主串，s为待匹配的模式串，st和ed分别记录当前STR的初始与结束位置

1Func UBerz(STR,s,st,ed)

2

3 If copy(STR,st,ed)=s

4Then Return(st,ed)

5Exit

6Else If pos(s,copy(STR,st,(ed+st) div 2))>0

7Then Return(UBerz(STR,s,st,(ed+st) div 2))

8Else If pos(s,copy(STR,(ed+st) div 2+1,ed))>0

9Then Return(UBerz(STR,s,(ed+st) div 2+1,ed))

10Else Return(Nil)

时间复杂度分析

为了简化分析，不妨设length(s)=1；

记s在STR[i]的概率为x[i]

则有x[i]={0 UBerz(STR,s,1,length(s))<>i

{1 UBerz(STR,s,1,length(s))=i

故有sigma(x[i]|i=1,2,3..length(STR))=0+0+...+0+1=1

结合伪代码(6)与(8)中的判断，则实际调用(6))的概率为

sigma(x[i]|i=st,st+1...,(st+ed) div 2)<

sigma(x[i]|i=1,2...st-1)+sigma(x[i]|i=st,st+1...,(st+ed) div 2)+sigma(x[i]|

i=(st+ed) div 2...length(STR))

=sigma(x[i]|i=1,2,3..length(STR))

=1

注意由yu不等式，sigma(x[i]|i=1,2...st-1)，sigma(x[i]|

i=(st+ed) div 2...length(STR))均大于零，

因此该算法的核心就在于上述的不等式在yu不等式的保证下是严格的。

该程序的时间复杂度为O(n)(*这里使用了大O表示法，如果读者对这个记号不是很清楚的话，可以在任意一本与信息学相关的书上找到，故在此不再赘述*)，而多次的实践证明该算法的实际时间复杂度远远小于理论上界，并且在40%的情况比经典的KMP算法效率更高，值得一提的是在29%的测试数据下，该算法的实际运行时间少于经典KMP算法的三分之一。