fork(1) download
copy 
  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
comments (?)
stdin
copy 
cd abсd ab
abcdabcd
stdout
copy 
Does not compute.
https://ideone.com/Z3AYH5
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!