dzsh算法是一種簡(jiǎn)化版的Z函數(shù)算法,用于字符串匹配和搜索。下面是一個(gè)實(shí)現(xiàn)dzsh算法的Lua腳本示例:
-- 計(jì)算dzsh數(shù)組
function computeDZSHArray(pattern)
local m = #pattern
local dzsh = {}
local l, r = 0, 0
for i = 2, m do
if i <= r then
dzsh[i] = math.min(r-i+1, dzsh[i-l+1])
end
while i+dzsh[i] <= m and pattern[i+dzsh[i]] == pattern[1+dzsh[i]] do
dzsh[i] = dzsh[i] + 1
end
if i+dzsh[i]-1 > r then
l, r = i, i+dzsh[i]-1
end
end
return dzsh
end
-- dzsh算法
function dzshSearch(text, pattern)
local n = #text
local m = #pattern
local dzsh = computeDZSHArray(pattern)
local matches = {}
local j = 1
for i = 1, n do
if text[i] == pattern[j] then
j = j + 1
if j > m then
table.insert(matches, i-m+1)
j = dzsh[j-1]+1
end
else
if j > 1 then
j = dzsh[j-1]+1
end
end
end
return matches
end
-- 測(cè)試
local text = "ABABDABACDABABCABAB"
local pattern = "ABABCABAB"
local matches = dzshSearch(text, pattern)
print("Pattern matches:")
for _, match in ipairs(matches) do
print(match)
end
在上面的代碼中,computeDZSHArray(pattern)
函數(shù)用于計(jì)算dzsh數(shù)組,該數(shù)組存儲(chǔ)了模式字符串中每個(gè)位置開始的最長(zhǎng)匹配前綴的長(zhǎng)度。dzshSearch(text, pattern)
函數(shù)用于在文本字符串中搜索模式字符串,并返回匹配的起始位置。
通過調(diào)用dzshSearch(text, pattern)
函數(shù),可以在文本字符串text
中搜索模式字符串pattern
,并將匹配的起始位置打印出來。