String Matching
这个问题已经被做烂了．．．
下面是C语言实现集合.
http://www-igm.univ-mlv.fr/~lecroq/string/
留个爪～
暴力解法：
暴力美啊～
"""
Programmer : EOF
Date : 2015.02.28
Code file : nsm.py
"""
def naive_string_matcher(T, P) :
if (T or P) is None :
return
n = len(T)
m = len(P)
for s in range(0, n-m+1) :
match = True
for i in range(0, m) :
if P[i] is not T[s+i] :
match = False
break
if match is True :
print "Pattern occurs with shift", s
#------------ for testing --------------------
string1 = "hello goodbye and hello"
string2 = "hello"
naive_string_matcher(string1, string2)
Rabin-Krap :
"""
Programmer : EOF
Code date : 2015.02.28
Code file : rkm.py
e-mail : [email protected]
"""
def rabin_karp_matcher(T, P, d, q) :
n = len(T)
m = len(P)
h = d**(m-1) % q
p = 0
t_0 = 0
t = [0 for i in range(0, n - m + 1)]
# preprosecessing
for i in range(0, m) :
p = ( d*p + ord(P[i]) ) % q
t[0] = (d*t[0] + ord(T[i])) % q
# matching
for s in range(0, n-m+1) :
match = True
if p is t[s] :
for i in range(0, m) :
if P[i] is not T[s+i] :
match = False
break
if match is True :
print "Pattern occurs with shift", s
if s < n-m :
t[s+1] = (d * ( t[s] - ord(T[s]) * h ) + ord(T[s+m]) ) % q
#------------ for testing --------------------
string1 = "hello goodbye and hello"
string2 = "hello"
rabin_karp_matcher(string1, string2, 10, 13)
KMP:
"""
Programmer : EOF
Code date : 2015.02.28
Code file : kmp.py
e-mail : [email protected]
Code description :
Here is a implementation of KMP which is a useful
algorithm for string matching.
"""
def kmp_matcher(T, P) :
n = len(T)
m = len(P)
pi = compute_prefix_function(P)
q = -1 # number of characters matched
for i in range(0, n) : # scan the text from left to right
while q > 0 and P[q+1] != T[i] :
q = pi[q] # next character doesn't match
if P[q+1] == T[i] :
q += 1 # next character matches
if (q+1) == m : # Is all of P matched ?
print "Pattern occurs with shift ", i-m
q = pi[q] # look for the next match
def compute_prefix_function(P) :
m = len(P)
pi = [-1 for i in range(0, m)]
k = -1 # Attention !
for q in range(1, m) :
while k > 0 and P[k+1] != P[q] :
k = pi[k]
if P[k+1] == P[q] :
k += 1
pi[q] = k
return pi
#-------------for testing----------------------
#string_1 = "hello goodbye and hello"
#string_2 = "hello"
string_1 = "abcabaabcabac"
string_2 = "abaa"
kmp_matcher(string_1, string_2)
PHP神人吐槽KMP
waiting for updates ... ...