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()
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
aabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbababababababababababababababab
ab ab ab ab ab ab ab ab ab ab ab ab ab ab ab 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