LCS

local serialization = require("serialization")
local unicode = require("unicode")

local max = math.max

local function longestCommonSubstring(str1, str2)
    local res = {length = 0, sequence = "", offset = 0}
    if str1 == nil or str2 == nil then
        return res
    end

    local sequence = ""
    local str1Len = unicode.len(str1)
    local str2Len = unicode.len(str2)
    local num = {}
    local maxlen = 0
    local lastSubsBegin = 0

    for i=0, str1Len do
        local subArray = {}
        for j=0, str2Len do
            subArray[j] = 0
        end
        num[i] = subArray
    end
    local thisSubsBegin = nil

    for i=1, str1Len do
        for j=1, str2Len do
            if unicode.sub(str1, i, i) ~= unicode.sub(str2, j, j) then
                num[i][j] = 0
            else
                if i == 0 or j == 0 then
                    num[i][j] = 1
                else
                    num[i][j] = 1 + num[i-1][j-1]
                end
                if num[i][j] > maxlen then
                    maxlen = num[i][j]
                    thisSubsBegin = i- num[i][j] + 1
                    if lastSubsBegin == thisSubsBegin then
                        sequence = sequence..unicode.sub(str1, i, i)
                    else
                        lastSubsBegin = thisSubsBegin
                        sequence = ""
                        sequence = sequence..unicode.sub(str1, lastSubsBegin, (i + 1) - lastSubsBegin)
                    end
                end
            end
        end
    end
    res["length"] = maxlen
    res["sequence"] = sequence
    res["offset"] = thisSubsBegin
    return res
end

print(serialization.serialize(longestCommonSubstring("This part of the","This is an important")))


local function longestCommonSubSequence(str1, str2)
    if (str1 == nil or str1 == "") or (str2 == nil or str2 == "") then
        return nil
    end
    local str1Len = unicode.len(str1)
    local str2Len = unicode.len(str2)
    local num = {}

    for i=0, str1Len do
        local subArray = {}
        for j=0, str2Len do
            subArray[j] = 0
        end
        num[i] = subArray
    end

    for i=0, str1Len do
        for j=0, str2Len do
            if unicode.sub(str1, i, i) == unicode.sub(str2, j, j) then
                if i == 0 or j == 0 then
                    num[i][j] = 1
                else
                    num[i][j] = 1 + num[i - 1][j - 1]
                end
            else
                if i == 0 and j == 0 then
                    num[i][j] = 0
                elseif i == 0 and j ~= 0 then
                    num[i][j] = max(0, num[i][j - 1])
                elseif i ~= 0 and j == 0 then
                    num[i][j] = max(0, num[i - 1][j])
                elseif i ~= 0 and j ~= 0 then
                    num[i][j] = max(num[i - 1][j], num[i][j - 1])
                end
            end
        end
    end
    return num
end

print(serialization.serialize(longestCommonSubSequence("This part of the","This is an important")))