count.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3
   4 struct state {
   5         struct state *fwd[256], *back, *qnext, *qprev;
   6         char *out;
   7         int count;
   8 };
   9
  10 struct state root, *head, *tail;
  11
  12 struct state *step(struct state *s, int c)
  13 {
  14         while (s) {
  15                 if (s->fwd[c])
  16                         return s->fwd[c];
  17                 s = s->back;
  18         }
  19         return &root;
  20 }
  21
  22 void insert(char *x)
  23 {
  24         struct state *s = &root;
  25         int c;
  26         for (char *y = x; c=*y++; ) {
  27                 if (!s->fwd[c])
  28                         s->fwd[c] = calloc(1, sizeof(struct state));
  29                 s = s->fwd[c];
  30         }
  31         s->out = x;
  32 }
  33
  34 void build(void)
  35 {
  36         struct state *s;
  37         head = tail = &root;
  38         while (head) {
  39                 for (int c=0; c<256; c++)
  40                         if (s = head->fwd[c]) {
  41                                 s->back = step(head->back, c);
  42                                 tail->qnext = s;
  43                                 s->qprev = tail;
  44                                 tail = s;
  45                         }
  46                 head = head->qnext;
  47         }
  48 }
  49
  50 void run(void)
  51 {
  52         struct state *s = &root;
  53         for (int c; (c = getchar()) != EOF;) {
  54                 s = step(s, c);
  55                 s->count++;
  56         }
  57 }
  58
  59 void count(void)
  60 {
  61         for (struct state *s=tail; s != &root; s=s->qprev) {
  62                 s->back->count += s->count;
  63                 if (s->out)
  64                         printf("%6d %s\n", s->count, s->out);
  65         }
  66 }
  67
  68 int main(int argc, char **argv)
  69 {
  70         for (int i=1; i<argc; i++)
  71                 insert(argv[i]);
  72         build();
  73         run();
  74         count();
  75         return 0;
  76 }