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