fork(1) 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 function reverse(t)
  26. local res = {}
  27. local l = #t
  28. for i = #t, 1, -1 do table.insert(res, t[i]) end
  29. return res
  30. end
  31.  
  32. local search_memo = {}
  33. local function search(words, str)
  34. local key = table.concat(words, " ") .. " " .. str
  35. if not search_memo[key] then
  36. if #words == 0 and str:len() == 0 then
  37. local result = {{}, {}}
  38. search_memo[key] = {result, true}
  39. return result, true
  40. end
  41. for _, w in ipairs(words) do
  42. local ana = str:sub(1, w:len())
  43. if are_anagramic(w, ana) then
  44. local result, success = search(remove_once(words, w), str:sub(w:len() + 1))
  45. if success then
  46. table.insert(result[1], ana)
  47. table.insert(result[2], w)
  48. search_memo[key] = {result, true}
  49. return result, true
  50. end
  51. end
  52. end
  53. search_memo[key] = {"huy tam", false }
  54. return "huy tam", false
  55. else
  56. return search_memo[key][1], search_memo[key][2]
  57. end
  58. end
  59.  
  60. local function main()
  61. local str1 = io.read()
  62. local words = {}
  63. for w in str1:gmatch "[%w%p]+" do
  64. table.insert(words, w)
  65. end
  66. local str2 = io.read()
  67. local result, success = search(words, str2)
  68. if success then
  69. print(table.concat(reverse(result[1]), " "))
  70. print(table.concat(reverse(result[2]), " "))
  71. else
  72. print(result)
  73. end
  74. end
  75.  
  76. main()
  77.  
Success #stdin #stdout 0.01s 2544KB
stdin
lalka, ty
ytllka,a
stdout
yt llka,a
ty lalka,