String Matching -- Brute Force + Rabin-Karp + KMP

本文主要是介绍String Matching -- Brute Force + Rabin-Karp + KMP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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 = Truefor i in range(0, m) :if P[i] is not T[s+i] :match = Falsebreakif 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      :   jasonleaster@gmail.com"""
def rabin_karp_matcher(T, P, d, q) :n = len(T)m = len(P)h = d**(m-1) % qp = 0t_0 = 0t = [0 for i in range(0, n - m + 1)]# preprosecessingfor i in range(0, m) :p = ( d*p + ord(P[i]) ) % qt[0] = (d*t[0] + ord(T[i])) % q# matchingfor s in range(0, n-m+1) :match = Trueif p is t[s] :for i in range(0, m) :if P[i] is not T[s+i] :match = Falsebreakif match is True :print "Pattern occurs with shift", sif 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      :   jasonleaster@gmail.comCode 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 matchedfor i in range(0, n) : # scan the text from left to rightwhile q > 0 and P[q+1] != T[i] :q = pi[q]       # next character doesn't matchif P[q+1] == T[i] :q += 1          # next character matchesif (q+1) == m :         # Is all of P matched ?print "Pattern occurs with shift ", i-mq = pi[q]       # look for the next matchdef 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 += 1pi[q] = kreturn pi#-------------for testing----------------------
#string_1 = "hello goodbye and hello"
#string_2 = "hello"
string_1 = "abcabaabcabac"
string_2 = "abaa"
kmp_matcher(string_1, string_2)