Wu-Manber算法是一種字符串匹配算法，用于高效地搜索字符串。它是一種混合算法，結(jié)合了Boyer-Moore和Knuth-Morris-Pratt算法的優(yōu)勢(shì)，可提供快速準(zhǔn)確的模式匹配。
Wu-Manber算法步驟
1.創(chuàng)建一個(gè)哈希表，將模式的每個(gè)可能子字符串映射到該子字符串出現(xiàn)的模式位置。
2.該哈希表用于快速識(shí)別文本中模式的潛在起始位置。
3.遍歷文本并將每個(gè)字符與模式中的相應(yīng)字符進(jìn)行比較。
4.如果字符匹配，則可以移動(dòng)到下一個(gè)字符并繼續(xù)比較。
5.如果字符不匹配，可以使用哈希表來(lái)確定在模式的下一個(gè)潛在起始位置之前可以跳過(guò)的最大字符數(shù)。
6.這允許算法快速跳過(guò)大部分文本，而不會(huì)錯(cuò)過(guò)任何潛在的匹配項(xiàng)。
Python實(shí)現(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)
登錄后復(fù)制
KMP和Wu-Manber算法之間的區(qū)別
KMP算法和Wu Manber算法都是字符串匹配算法，也就是說(shuō)它們都是用來(lái)在一個(gè)較大的字符串中尋找一個(gè)子串。這兩種算法具有相同的時(shí)間復(fù)雜度，這意味著它們?cè)谒惴ㄟ\(yùn)行所需的時(shí)間方面具有相同的性能特征。
但是，它們之間存在一些差異：
1、KMP算法使用預(yù)處理步驟生成部分匹配表，用于加快字符串匹配過(guò)程。這使得當(dāng)搜索的模式相對(duì)較長(zhǎng)時(shí)，KMP算法比Wu Manber算法更有效。
2、Wu Manber算法使用不同的方法來(lái)進(jìn)行字符串匹配，它將模式劃分為多個(gè)子模式，并使用這些子模式在文本中搜索匹配項(xiàng)。這使得Wu Manber算法在搜索的模式相對(duì)較短時(shí)比KMP算法更有效。
