luaスクリプトでdzshアルゴリズムを実装する方法

2年 ago
芽依, 雨夜
1 minute

DZSは、文字列マッチングと検索に使用される、Zファンクションの簡略化版です。以下は、LuaスクリプトでDZSを実装した例です。

-- 计算dzsh数组
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

-- 测试
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)関数は、パターン文字列内の各位置から始まる最長一致接頭辞の長さを格納したdzsh配列を計算します。dzshSearch(text, pattern)関数は、テキスト文字列内でパターン文字列を検索し、一致の開始位置を返します。

dzshSearch(text, pattern)関数を呼び出して、テキスト文字列text内でパターン文字列patternを検索し、マッチした開始位置を出力します。

bannerAds