fork(1) download
  1. import java.util.*;
  2.  
  3. class CharBag implements Comparable<CharBag> {
  4. public static int CHAR_POWER = 2048;
  5.  
  6. private int[] map = new int[CHAR_POWER];
  7. private int count = 0;
  8. private String word;
  9. private CharBag copy;
  10.  
  11. CharBag() {}
  12.  
  13. CharBag(String word) {
  14. this.word = word;
  15. for (int i = 0; i < word.length(); i++) {
  16. this.add(word.charAt(i));
  17. }
  18. copy = new CharBag();
  19. copy.word = word;
  20. }
  21.  
  22. public String getWord() {
  23. return word;
  24. }
  25.  
  26. public int getCount() {
  27. return count;
  28. }
  29.  
  30. public void add(char c) {
  31. map[(int) c]++;
  32. count++;
  33. }
  34.  
  35. public boolean remove(char c) {
  36. int index = (int) c;
  37. if (map[index] > 0) {
  38. map[index]--;
  39. count--;
  40. return true;
  41. } else {
  42. return false;
  43. }
  44. }
  45.  
  46. public boolean checkAnagramDestructive(String anagram) {
  47. for (int i = 0; i < anagram.length(); i++) {
  48. char c = anagram.charAt(i);
  49. if (!this.remove(c)) {
  50. return false;
  51. }
  52. }
  53. return this.count == 0;
  54. }
  55.  
  56. private void makeCopy() {
  57. copy.count = count;
  58. System.arraycopy(map, 0, copy.map, 0, CHAR_POWER);
  59. }
  60.  
  61. public boolean checkAnagram(String anagram) {
  62. makeCopy();
  63. return copy.checkAnagramDestructive(anagram);
  64. }
  65.  
  66. @Override
  67. public int compareTo(CharBag o) {
  68. return Integer.compare(this.count, o.count);
  69. }
  70. }
  71.  
  72. public class Main {
  73. public static void main(String[] args) {
  74. Scanner scanner = new Scanner(System.in);
  75. String str1 = scanner.nextLine();
  76. String[] words = str1.split("\\s+");
  77. List<CharBag> bags = new ArrayList<>();
  78. for (String word : words) {
  79. bags.add(new CharBag(word));
  80. }
  81. String str2 = scanner.nextLine();
  82. List<CharBag> matchingBags = new ArrayList<>(words.length);
  83. List<String> anagrams = new ArrayList<>(words.length);
  84. List<String> resultWords = new ArrayList<>(words.length);
  85. while (!(str2.isEmpty() || bags.isEmpty())) {
  86. for (CharBag bag : bags) {
  87. if (bag.checkAnagram(str2.substring(0, bag.getCount()))) {
  88. matchingBags.add(bag);
  89. }
  90. }
  91. if (matchingBags.isEmpty()) {
  92. System.out.println("Does not compute.");
  93. return;
  94. }
  95. CharBag bagWithMaxLength = Collections.min(matchingBags);
  96. int split = bagWithMaxLength.getCount();
  97. anagrams.add(str2.substring(0, split));
  98. resultWords.add(bagWithMaxLength.getWord());
  99. str2 = str2.substring(split);
  100. bags.remove(bagWithMaxLength);
  101. matchingBags.clear();
  102. }
  103. if (!str2.isEmpty()) {
  104. System.out.println("Too few words!");
  105. } else if (!bags.isEmpty()) {
  106. System.out.println("Too many words!");
  107. } else {
  108. for (String ana : anagrams) {
  109. System.out.print(ana + " ");
  110. }
  111. System.out.println();
  112. for (String w : resultWords) {
  113. System.out.print(w + " ");
  114. }
  115. }
  116. }
  117. }
Success #stdin #stdout 0.1s 380736KB
stdin
cd abсd ab
abcdabcd
stdout
Does not compute.