fork(3) download
copy 
  1. local sort_memo = {}
  2. local function string_sort(str) 
  3.   if not sort_memo[str] then 
  4.     local t = {}
  5.     for c in str:gmatch "." do  
  6.       table.insert(t, c)
  7.     end
  8.     table.sort(t)
  9.     sort_memo[str] = table.concat(t)
  10.   end
  11.   return sort_memo[str]
  12. end
  13.  
  14. local function are_anagramic(w1, w2) return string_sort(w1) == string_sort(w2) end
  15.  
  16. local function remove_once(t, e)
  17.   local res = {}
  18.   local removed = false
  19.   for _, o in ipairs(t) do
  20.     if o ~= e or removed then table.insert(res, o) else removed = true end
  21.   end
  22.   return res
  23. end
  24.  
  25. local function reverse(t)
  26.   local res = {}
  27.   local l = #t
  28.   for i = #t, 1, -1 do table.insert(res, t[i]) end
  29.   return res
  30. end
  31.  
  32. local search_memo = {}
  33. local function search(words, str)
  34.   local key = table.concat(words, " ") .. " " .. str
  35.   if not search_memo[key] then
  36.     if #words == 0 and str:len() == 0 then
  37.       local result =  {{}, {}}
  38.       search_memo[key] = {result, true}
  39.       return result, true
  40.     end
  41.     for _, w in ipairs(words) do
  42.       local ana = str:sub(1, w:len())
  43.       if are_anagramic(w, ana) then
  44.         local result, success = search(remove_once(words, w), str:sub(w:len() + 1))
  45.         if success then 
  46.           table.insert(result[1], ana)
  47.           table.insert(result[2], w)
  48.           search_memo[key] = {result, true}
  49.           return result, true
  50.         end
  51.       end
  52.     end
  53.     search_memo[key] = {"huy tam", false }
  54.     return "huy tam", false
  55.   else
  56.     return search_memo[key][1], search_memo[key][2]
  57.   end
  58. end
  59.  
  60. local function main()
  61.   local str1 = io.read()
  62.   local words = {}
  63.   for w in str1:gmatch "%w+" do
  64.     table.insert(words, w)
  65.   end
  66.   local str2 = io.read()
  67.   local result, success = search(words, str2)
  68.   if success then
  69.      print(table.concat(reverse(result[1]), " "))
  70.      print(table.concat(reverse(result[2]), " "))
  71.   else
  72.     print(result)
  73.   end
  74. end
  75.  
  76. main()
Success #stdin #stdout 0.02s 2544KB
comments (?)
stdin
copy 
аб цд
абцд
stdout
copy 
huy tam
https://ideone.com/xBLCjz
language:
Lua (luac 5.3.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!