/* Counting words. MM scribebat me per III Id. Mai. MMDCCLIX AUC. */

#include <stdio.h>
#include <stdlib.h>

struct state {					// jeden stav automatu
  struct state *fwd[256], *back;		// hrany dopředné a zpětná
  struct state *qnext, *qprev;			// předchůdce a následník ve frontě
  char *out;					// které slovo v tomto stavu končí
  int count;					// počet průchodů stavem
};

struct state root;				// počáteční stav (kořen stromu)
struct state *head, *tail;			// první a poslední ve frontě

struct state *step(struct state *s, int c)	// jeden krok automatu 
{                                               //   (včetně vracení se po zpětných hranách)
  while (s) {
    if (s->fwd[c])				// hrr na ně!
      return s->fwd[c];
    s = s->back;				// a když to nejde, tož cófnem
  }
  return &root;
}

void insert(char *x)				// vložení jednoho slova do stromu
{
  struct state *s = &root;
  int c;
  for (char *y = x; c=*y++; ) {
    if (!s->fwd[c])
      s->fwd[c] = calloc(1, sizeof(struct state));
    s = s->fwd[c];
  }
  s->out = x;
}

void build(void)				// konstrukce zpětných hran přesně podle kuchařky
{
  struct state *s;
  head = tail = &root;
  while (head) {
    for (int c=0; c<256; c++)
      if (s = head->fwd[c]) {
	s->back = step(head->back, c);
	tail->qnext = s;
	s->qprev = tail;
	tail = s;
      }
    head = head->qnext;
  }
}

void run(void)					// projití celého vstupu s počítáním průchodů stavy
{
  struct state *s = &root;
  for (int c; (c = getchar()) != EOF;) {
    s = step(s, c);
    s->count++;
  }
}

void count(void)				// propagování počtů po zpětných hranách
{
  for (struct state *s=tail; s != &root; s=s->qprev) {
    s->back->count += s->count;
    if (s->out)					// ... a vypisování četností slov
      printf("%6d %s\n", s->count, s->out);
  }
}

int main(int argc, char **argv)			// main sweet main :)
{
  for (int i=1; i<argc; i++)
    insert(argv[i]);
  build();
  run();
  count();
  return 0;
}