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 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+" do
    table.insert(words, w)
  end
  local str2 = io.read()
  local result, success = search(words, str2)
  if success then
     print(table.concat(result[1], " "))
     print(table.concat(result[2], " "))
  else
    print(result)
  end
end

main()
Success #stdin #stdout 0.03s 2500KB
stdin
ab ab ab ab ab abab abab abab abab abab ab ab ab ab ab abab abab abab abab abab ab ab ab ab ab abab abab
abababababababababababababababaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabb
stdout
aabb aabb aabb aabb aabb aabb aabb aabb aabb aabb aabb aabb ab ab ab ab ab ab ab ab ab ab ab ab ab ab ab
abab abab abab abab abab abab abab abab abab abab abab abab ab ab ab ab ab ab ab ab ab ab ab ab ab ab ab