Wu-Manber算法是一種字符串匹配算法，用于高效地搜索字符串。它是一種混合算法，結合了Boyer-Moore和Knuth-Morris-Pratt算法的優(yōu)勢，可提供快速準確的模式匹配。
Wu-Manber算法步驟
1.創(chuàng)建一個哈希表，將模式的每個可能子字符串映射到該子字符串出現(xiàn)的模式位置。
2.該哈希表用于快速識別文本中模式的潛在起始位置。
3.遍歷文本并將每個字符與模式中的相應字符進行比較。
4.如果字符匹配，則可以移動到下一個字符并繼續(xù)比較。
5.如果字符不匹配，可以使用哈希表來確定在模式的下一個潛在起始位置之前可以跳過的最大字符數(shù)。
6.這允許算法快速跳過大部分文本，而不會錯過任何潛在的匹配項。
Python實現(xiàn)Wu-Manber算法
# Define the hash_pattern() function to generate
# a hash for each subpattern
def hashPattern(pattern, i, j):
h = 0
for k in range(i, j):
h = h * 256 + ord(pattern[k])
return h
# Define the Wu Manber algorithm
def wuManber(text, pattern):
# Define the length of the pattern and
# text
m = len(pattern)
n = len(text)
# Define the number of subpatterns to use
s = 2
# Define the length of each subpattern
t = m // s
# Initialize the hash values for each
# subpattern
h = [0] * s
for i in range(s):
h[i] = hashPattern(pattern, i * t, (i + 1) * t)
# Initialize the shift value for each
# subpattern
shift = [0] * s
for i in range(s):
shift[i] = t * (s - i - 1)
# Initialize the match value
match = False
# Iterate through the text
for i in range(n - m + 1):
# Check if the subpatterns match
for j in range(s):
if hashPattern(text, i + j * t, i + (j + 1) * t) != h[j]:
break
else:
# If the subpatterns match, check if
# the full pattern matches
if text[i:i + m] == pattern:
print("Match found at index", i)
match = True
# Shift the pattern by the appropriate
# amount
for j in range(s):
if i + shift[j] < n - m + 1:
break
else:
i += shift[j]
# If no match was found, print a message
if not match:
print("No match found")
# Driver Code
text = "the cat sat on the mat"
pattern = "the"
# Function call
wuManber(text, pattern)
登錄后復制
KMP和Wu-Manber算法之間的區(qū)別
KMP算法和Wu Manber算法都是字符串匹配算法，也就是說它們都是用來在一個較大的字符串中尋找一個子串。這兩種算法具有相同的時間復雜度，這意味著它們在算法運行所需的時間方面具有相同的性能特征。
但是，它們之間存在一些差異：
1、KMP算法使用預處理步驟生成部分匹配表，用于加快字符串匹配過程。這使得當搜索的模式相對較長時，KMP算法比Wu Manber算法更有效。
2、Wu Manber算法使用不同的方法來進行字符串匹配，它將模式劃分為多個子模式，并使用這些子模式在文本中搜索匹配項。這使得Wu Manber算法在搜索的模式相對較短時比KMP算法更有效。
