fork(1) download
  1. local function string_sort(str)
  2. local t = {}
  3. for c in str:gmatch "." do
  4. table.insert(t, c)
  5. end
  6. table.sort(t)
  7. return table.concat(t)
  8. end
  9.  
  10. local function are_anagramic(w1, w2) return string_sort(w1) == string_sort(w2) end
  11.  
  12. local function remove_once(t, e)
  13. local res = {}
  14. local removed = false
  15. for _, o in ipairs(t) do
  16. if o ~= e or removed then table.insert(res, o) else removed = true end
  17. end
  18. return res
  19. end
  20.  
  21. local function search(words, str)
  22. if #words == 0 and str:len() == 0 then return {{}, {}}, true end
  23. for _, w in ipairs(words) do
  24. local ana = str:sub(1, w:len())
  25. if are_anagramic(w, ana) then
  26. local result, success = search(remove_once(words, w), str:sub(w:len() + 1))
  27. if success then
  28. table.insert(result[1], ana)
  29. table.insert(result[2], w)
  30. return result, true
  31. end
  32. end
  33. end
  34. return "huy tam", false
  35. end
  36.  
  37. local function main()
  38. local str1 = io.read()
  39. local words = {}
  40. for w in str1:gmatch "%w+" do
  41. table.insert(words, w)
  42. end
  43. local str2 = io.read()
  44. local result, success = search(words, str2)
  45. if success then
  46. print(table.concat(result[1], " "))
  47. print(table.concat(result[2], " "))
  48. else
  49. print(result)
  50. end
  51. end
  52.  
  53. main()
Time limit exceeded #stdin #stdout 5s 2540KB
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
Standard output is empty