#include <cmath>
#include <iomanip>
#include <iostream>
#include <string>

const int maxx = 10000;

struct HashLink
{ string s;
  HashLink * next;
  HashLink(string s, HashLink * n)
  { this->s = s;
    next = n; } };

struct HashList
{ HashLink * first;

  HashList()
  { first = NULL; }

  bool add(string s)
  { HashLink * ptr = first;
    while (ptr != NULL)
    { if (s == ptr->s)
        return true;
      ptr = ptr->next; }
    first = new HashLink(s, first);
    return false; }

  int length()
  { int n = 0;
    HashLink * ptr = first;
    while (ptr != NULL)
    { n += 1;
      ptr = ptr->next; }
    return n; } };

unsigned int hash(string s)
{ unsigned int h = 278364;
  int len = s.length();
  for (int i = 0; i < len; i += 1)
    h = h * 69 + s[i];
  return h % maxx; }

void main()
{ HashList table[maxx];
  int news = 0, olds = 0, clashes = 0, total = 0;
  cout << "Type some strings.\n";

  while (true)
  { string s;
    cin >> s;
    if (cin.eof())
      break;
    total += 1;
    int x = hash(s);

    bool already = table[x].add(s); }

  int counts[20];
  for (int i = 0; i<20; i += 1)
    counts[i] = 0;

  for (int i = 0; i<maxx; i += 1)
  { int len = table[i].length();
    if (len < 19)
      counts[len] += 1;
    else
      counts[19] += 1; }

  double lam = total / (double)maxx;
  double p = maxx * exp(-lam);
  for (int i = 0; i<19; i += 1)
  { cout << "length " << setw(2) << i << " occurred "
         << setw(7) << counts[i] << " times, expected "
         << setw(7) << (int)p << "\n";
    p = p * lam / (i+1); }
  cout << counts[19] << " too long\n"; }