fork(1) download
local sort_memo = {}
local function string_sort(str) 
  if not sort_memo[str] then 
    local t = {}
    for c in str:gmatch "." do  
      table.insert(t, c)
    end
    table.sort(t)
    sort_memo[str] = table.concat(t)
  end
  return sort_memo[str]
end

local function are_anagramic(w1, w2) return string_sort(w1) == string_sort(w2) end

local function remove_once(t, e)
  local res = {}
  local removed = false
  for _, o in ipairs(t) do
    if o ~= e or removed then table.insert(res, o) else removed = true end
  end
  return res
end

local function reverse(t)
  local res = {}
  local l = #t
  for i = #t, 1, -1 do table.insert(res, t[i]) end
  return res
end

local search_memo = {}
local function search(words, str)
  local key = table.concat(words, " ") .. " " .. str
  if not search_memo[key] then
    if #words == 0 and str:len() == 0 then
      local result =  {{}, {}}
      search_memo[key] = {result, true}
      return result, true
    end
    for _, w in ipairs(words) do
      local ana = str:sub(1, w:len())
      if are_anagramic(w, ana) then
        local result, success = search(remove_once(words, w), str:sub(w:len() + 1))
        if success then 
          table.insert(result[1], ana)
          table.insert(result[2], w)
          search_memo[key] = {result, true}
          return result, true
        end
      end
    end
    search_memo[key] = {"huy tam", false }
    return "huy tam", false
  else
    return search_memo[key][1], search_memo[key][2]
  end
end

local function main()
  local str1 = io.read()
  local words = {}
  for w in str1:gmatch "[%w%p]+" do
    table.insert(words, w)
  end
  local str2 = io.read()
  local result, success = search(words, str2)
  if success then
     print(table.concat(reverse(result[1]), " "))
     print(table.concat(reverse(result[2]), " "))
  else
    print(result)
  end
end

main()
Success #stdin #stdout 0.01s 2544KB
stdin
lalka, ty
ytllka,a
stdout
yt llka,a
ty lalka,