吳炳璋算法
一個基於遞歸的二分查找算法，由於其證明極其繁瑣，故直接給出偽代碼：
//STR為主串，s為待匹配的模式串，st和ed分別記錄當前STR的初始與結束位置
1Func UBerz(STR,s,st,ed)
2
3 If copy(STR,st,ed)=s
4 Then Return(st,ed)
5 Exit
6 Else If pos(s,copy(STR,st,(ed+st) div 2))>0
7 Then Return(UBerz(STR,s,st,(ed+st) div 2))
8 Else If pos(s,copy(STR,(ed+st) div 2+1,ed))>0
9 Then Return(UBerz(STR,s,(ed+st) div 2+1,ed))
10 Else 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算法的三分之一。
