2012年1月17日 星期二
2011年12月23日 星期五
2011年12月21日 星期三
2011年12月3日 星期六
Substring matching
Find if string P in T?
Rabin-Karp algorithm
Hashing P and each substring of T
compare hash value to examine
Trick: Hashing substring of T can be reduced to 1 step
Pseudo code:
Rabin-Karp-matcher(T,P,d,q)
n= length(P)
m=length(T)
h= d^(m-1) mod q
p=0
t0=0
for i=1,m //Processing
p = (dp +P[i]) mod q
t_0 = (dt + T[i]) mod q
end for
for s=0,n-m //Matching
if p=t_s
if P[i..m]=T[s+1....s+m]
print "Find it!"
end if
end if
if s<n-m
t_(s+1) =( d(t_s - T[s+1]h ) + T[s+m+1] ) mod q
end if
end for
Rabin-Karp algorithm
Hashing P and each substring of T
compare hash value to examine
Trick: Hashing substring of T can be reduced to 1 step
Pseudo code:
Rabin-Karp-matcher(T,P,d,q)
n= length(P)
m=length(T)
h= d^(m-1) mod q
p=0
t0=0
for i=1,m //Processing
p = (dp +P[i]) mod q
t_0 = (dt + T[i]) mod q
end for
for s=0,n-m //Matching
if p=t_s
if P[i..m]=T[s+1....s+m]
print "Find it!"
end if
end if
if s<n-m
t_(s+1) =( d(t_s - T[s+1]h ) + T[s+m+1] ) mod q
end if
end for
2011年11月11日 星期五
2011年11月8日 星期二
訂閱：
文章 (Atom)