快速查找算法
//intensive case character
% j V! \9 z2 Aint findPos(char *pattern,char *destionStr,int startPos){
0 G. d3 f, U! }2 }) {$ j+ S- L int delta[128];//the delta
n7 i. e5 p$ a' f int i;//use for [for]9 c9 F; Y9 V$ C' n
int patternLen=strlen(pattern);
9 D5 r8 ]8 x0 c1 f! N! w9 y int destionLen=strlen(destionStr);
" M1 c4 `& E/ j7 E( \ int t=startPos+patternLen;
" b+ J# B7 R) V3 B) I: D6 t int p=patternLen;
) O9 U! T% A( r0 C3 n0 F% R1 q+ h0 }" x$ F/ B V! E
for(i=0;i<128;i++)//init every char's delta' ?. ]( A, _3 B% Z# B9 Y& q$ h3 x
delta=patternLen;
% B* d' G, f0 ]! |1 [/ Z/ {% E$ P" K" r$ p* S
for(i=1;i<=patternLen;i++){//init patter char's delta
# A4 ]3 P2 v" T: L! ^" o* }1 w delta[pattern[i-1]]=patternLen-i;0 I. e: {4 G1 C5 U9 ]/ J
}
- c$ {0 W/ G2 R2 [6 j while(t<=destionLen){
+ T2 ?) @9 M. V5 ?# g p=patternLen;# |; V/ D5 ?: M5 K
while(pattern[p-1]==destionStr[t-1]){- B- V2 ^ G) t4 z* O+ D; V
if(p>1){% D! a" M- J+ i3 j1 c0 C
p--;
+ q5 \* N) c' M! ]/ U; X% [0 \ t--;
1 ?( b* l( B5 p% }4 O9 ] }' P0 L1 L3 R4 V) m$ a
else1 D% g9 k( b& P( o4 Z
return t;- [/ W% `; T. L) w4 f) M* m8 F
}
+ M7 d( V: v7 p+ W( {7 _ t+=delta[destionStr[t-1]];
4 f- K2 ]/ W. ` }+ f; T* R4 C ?) I8 I. ~
return -1;
8 `" Q3 M, ?2 a; @0 }& W6 t% ^/ P}
