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( )
bG9jYWwgc29ydF9tZW1vID0ge30KbG9jYWwgZnVuY3Rpb24gc3RyaW5nX3NvcnQoc3RyKSAKICBpZiBub3Qgc29ydF9tZW1vW3N0cl0gdGhlbiAKICAgIGxvY2FsIHQgPSB7fQogICAgZm9yIGMgaW4gc3RyOmdtYXRjaCAiLiIgZG8gIAogICAgICB0YWJsZS5pbnNlcnQodCwgYykKICAgIGVuZAogICAgdGFibGUuc29ydCh0KQogICAgc29ydF9tZW1vW3N0cl0gPSB0YWJsZS5jb25jYXQodCkKICBlbmQKICByZXR1cm4gc29ydF9tZW1vW3N0cl0KZW5kCgpsb2NhbCBmdW5jdGlvbiBhcmVfYW5hZ3JhbWljKHcxLCB3MikgcmV0dXJuIHN0cmluZ19zb3J0KHcxKSA9PSBzdHJpbmdfc29ydCh3MikgZW5kCgpsb2NhbCBmdW5jdGlvbiByZW1vdmVfb25jZSh0LCBlKQogIGxvY2FsIHJlcyA9IHt9CiAgbG9jYWwgcmVtb3ZlZCA9IGZhbHNlCiAgZm9yIF8sIG8gaW4gaXBhaXJzKHQpIGRvCiAgICBpZiBvIH49IGUgb3IgcmVtb3ZlZCB0aGVuIHRhYmxlLmluc2VydChyZXMsIG8pIGVsc2UgcmVtb3ZlZCA9IHRydWUgZW5kCiAgZW5kCiAgcmV0dXJuIHJlcwplbmQKCmxvY2FsIHNlYXJjaF9tZW1vID0ge30KbG9jYWwgZnVuY3Rpb24gc2VhcmNoKHdvcmRzLCBzdHIpCiAgbG9jYWwga2V5ID0gdGFibGUuY29uY2F0KHdvcmRzLCAiICIpIC4uICIgIiAuLiBzdHIKICBpZiBub3Qgc2VhcmNoX21lbW9ba2V5XSB0aGVuCiAgICBpZiAjd29yZHMgPT0gMCBhbmQgc3RyOmxlbigpID09IDAgdGhlbgogICAgICBsb2NhbCByZXN1bHQgPSAge3t9LCB7fX0KICAgICAgc2VhcmNoX21lbW9ba2V5XSA9IHtyZXN1bHQsIHRydWV9CiAgICAgIHJldHVybiByZXN1bHQsIHRydWUKICAgIGVuZAogICAgZm9yIF8sIHcgaW4gaXBhaXJzKHdvcmRzKSBkbwogICAgICBsb2NhbCBhbmEgPSBzdHI6c3ViKDEsIHc6bGVuKCkpCiAgICAgIGlmIGFyZV9hbmFncmFtaWModywgYW5hKSB0aGVuCiAgICAgICAgbG9jYWwgcmVzdWx0LCBzdWNjZXNzID0gc2VhcmNoKHJlbW92ZV9vbmNlKHdvcmRzLCB3KSwgc3RyOnN1Yih3OmxlbigpICsgMSkpCiAgICAgICAgaWYgc3VjY2VzcyB0aGVuIAogICAgICAgICAgdGFibGUuaW5zZXJ0KHJlc3VsdFsxXSwgYW5hKQogICAgICAgICAgdGFibGUuaW5zZXJ0KHJlc3VsdFsyXSwgdykKICAgICAgICAgIHNlYXJjaF9tZW1vW2tleV0gPSB7cmVzdWx0LCB0cnVlfQogICAgICAgICAgcmV0dXJuIHJlc3VsdCwgdHJ1ZQogICAgICAgIGVuZAogICAgICBlbmQKICAgIGVuZAogICAgc2VhcmNoX21lbW9ba2V5XSA9IHsiaHV5IHRhbSIsIGZhbHNlIH0KICAgIHJldHVybiAiaHV5IHRhbSIsIGZhbHNlCiAgZWxzZQogICAgcmV0dXJuIHNlYXJjaF9tZW1vW2tleV1bMV0sIHNlYXJjaF9tZW1vW2tleV1bMl0KICBlbmQKZW5kCgpsb2NhbCBmdW5jdGlvbiBtYWluKCkKICBsb2NhbCBzdHIxID0gaW8ucmVhZCgpCiAgbG9jYWwgd29yZHMgPSB7fQogIGZvciB3IGluIHN0cjE6Z21hdGNoICIldysiIGRvCiAgICB0YWJsZS5pbnNlcnQod29yZHMsIHcpCiAgZW5kCiAgbG9jYWwgc3RyMiA9IGlvLnJlYWQoKQogIGxvY2FsIHJlc3VsdCwgc3VjY2VzcyA9IHNlYXJjaCh3b3Jkcywgc3RyMikKICBpZiBzdWNjZXNzIHRoZW4KICAgICBwcmludCh0YWJsZS5jb25jYXQocmVzdWx0WzFdLCAiICIpKQogICAgIHByaW50KHRhYmxlLmNvbmNhdChyZXN1bHRbMl0sICIgIikpCiAgZWxzZQogICAgcHJpbnQocmVzdWx0KQogIGVuZAplbmQKCm1haW4oKQ==