package amphis;

import java.io.BufferedReader;
import java.io.File;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collection;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Scanner;

/* utilisation : java Amphi6b fichier
 *   lit tous les mots du fichier
 *   puis, en boucle, lit un préfixe sur l'entrée standard
 *   et affiche tous les mots ayant ce préfixe
 */

// les mots sont stockés dans un arbre de préfixes
class Trie {

  private boolean word;
  private final Map<Character, Trie> branches;

  Trie() {
    this.word = false;
    this.branches = new HashMap<Character, Trie>();
  }

  void add(String s) {
    Trie t = this;
    for (int i = 0; i < s.length(); i++) { // invariant t != null
      char c = s.charAt(i);
      Map<Character, Trie> b = t.branches;
      t = b.get(c);
      if (t == null) {
        t = new Trie();
        b.put(c, t);
      }
    }
    t.word = true;
  }

  int size() {
    int s = 0;
    if (this.word) s++;
    for (Trie b: this.branches.values())
      s += b.size();
    return s;
  }

  Collection<String> below(String w) {
    Collection<String> coll = new LinkedList<>();
    Trie t = this;
    for (int i = 0; i < w.length(); i++) { // t != null
      t = t.branches.get(w.charAt(i));
      if (t == null) return coll;
    }
    t.collect(w, coll);
    return coll;
  }
  
  void collect(String prefix, Collection<String> coll) {
    if (this.word) coll.add(prefix);
    for (Character c: this.branches.keySet())
      this.branches.get(c).collect(prefix + c, coll);
  }
  
}

public class Amphi6b {

  public static void main(String[] args) throws IOException {
    Scanner sc = new Scanner(new File("jules-verne.txt"));
    sc.useDelimiter("[\\p{javaWhitespace}«»\\p{Punct}]+");
    Trie t = new Trie();
    while (sc.hasNext())
      t.add(sc.next());
    sc.close();
    System.out.println(t.size() + " mots");
    
    BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
    while (true) {
      String p = r.readLine();
      if (p == null)
        break;
      Collection<String> c = t.below(p);
      System.out.println(c.size() + " mots commençant par '" + p + "'");
      for (String s : c)
        System.out.print(s + " ");
      System.out.println();
    }
  }

}