MeXaN1cK

LCS

Mar 7th, 2021 (edited)
709
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. local serialization = require("serialization")
  2. local unicode = require("unicode")
  3.  
  4. local max = math.max
  5.  
  6. local function longestCommonSubstring(str1, str2)
  7.     local res = {length = 0, sequence = "", offset = 0}
  8.     if str1 == nil or str2 == nil then
  9.         return res
  10.     end
  11.    
  12.     local sequence = ""
  13.     local str1Len = unicode.len(str1)
  14.     local str2Len = unicode.len(str2)
  15.     local num = {}
  16.     local maxlen = 0
  17.     local lastSubsBegin = 0
  18.    
  19.     for i=0, str1Len do
  20.         local subArray = {}
  21.         for j=0, str2Len do
  22.             subArray[j] = 0
  23.         end
  24.         num[i] = subArray
  25.     end
  26.     local thisSubsBegin = nil
  27.    
  28.     for i=1, str1Len do
  29.         for j=1, str2Len do
  30.             if unicode.sub(str1, i, i) ~= unicode.sub(str2, j, j) then
  31.                 num[i][j] = 0
  32.             else
  33.                 if i == 0 or j == 0 then
  34.                     num[i][j] = 1
  35.                 else
  36.                     num[i][j] = 1 + num[i-1][j-1]
  37.                 end
  38.                 if num[i][j] > maxlen then
  39.                     maxlen = num[i][j]
  40.                     thisSubsBegin = i- num[i][j] + 1
  41.                     if lastSubsBegin == thisSubsBegin then
  42.                         sequence = sequence..unicode.sub(str1, i, i)
  43.                     else
  44.                         lastSubsBegin = thisSubsBegin
  45.                         sequence = ""
  46.                         sequence = sequence..unicode.sub(str1, lastSubsBegin, (i + 1) - lastSubsBegin)
  47.                     end
  48.                 end
  49.             end
  50.         end
  51.     end
  52.     res["length"] = maxlen
  53.     res["sequence"] = sequence
  54.     res["offset"] = thisSubsBegin
  55.     return res
  56. end
  57.  
  58. print(serialization.serialize(longestCommonSubstring("This part of the","This is an important")))
  59.  
  60.  
  61. local function longestCommonSubSequence(str1, str2)
  62.     if (str1 == nil or str1 == "") or (str2 == nil or str2 == "") then
  63.         return nil
  64.     end
  65.     local str1Len = unicode.len(str1)
  66.     local str2Len = unicode.len(str2)
  67.     local num = {}
  68.    
  69.     for i=0, str1Len do
  70.         local subArray = {}
  71.         for j=0, str2Len do
  72.             subArray[j] = 0
  73.         end
  74.         num[i] = subArray
  75.     end
  76.    
  77.     for i=0, str1Len do
  78.         for j=0, str2Len do
  79.             if unicode.sub(str1, i, i) == unicode.sub(str2, j, j) then
  80.                 if i == 0 or j == 0 then
  81.                     num[i][j] = 1
  82.                 else
  83.                     num[i][j] = 1 + num[i - 1][j - 1]
  84.                 end
  85.             else
  86.                 if i == 0 and j == 0 then
  87.                     num[i][j] = 0
  88.                 elseif i == 0 and j ~= 0 then
  89.                     num[i][j] = max(0, num[i][j - 1])
  90.                 elseif i ~= 0 and j == 0 then
  91.                     num[i][j] = max(0, num[i - 1][j])
  92.                 elseif i ~= 0 and j ~= 0 then
  93.                     num[i][j] = max(num[i - 1][j], num[i][j - 1])
  94.                 end
  95.             end
  96.         end
  97.     end
  98.     return num
  99. end
  100.  
  101. print(serialization.serialize(longestCommonSubSequence("This part of the","This is an important")))
RAW Paste Data