Lua公共子序列：双串比对的最长匹配

local function lcs(a, b, i, j)
    if i == 0 or j == 0 then return 0 end
    if a:sub(i, i) == b:sub(j, j) then
        return lcs(a, b, i - 1, j - 1) + 1
    end
    return math.max(lcs(a, b, i - 1, j),
                    lcs(a, b, i, j - 1))
end

local function lcsTable(a, b)
    local m, n = #a, #b
    local dp = {}
    for i = 0, m do dp[i] = {} end
    for i = 1, m do
        for j = 1, n do
            if a:sub(i, i) == b:sub(j, j) then
                dp[i][j] = (dp[i - 1][j - 1] or 0) + 1
            else
                dp[i][j] = math.max(dp[i - 1][j] or 0,
                    dp[i][j - 1] or 0)
            end
        end
    end
    return dp[m][n]
end
local p = getplayerbyname("lcs01")
sendmsg(p, 1, "最长公共 " .. lcsTable("a1b2c3", "x1y2z9"))