#include #include #include #include #include #include size_t hash(const char* word) { size_t x; for (x=0; *word; ++word) x = (x + (x << 5)) ^ *word; return x; } #define HASHTABSIZE 65536 struct node { unsigned long count; struct node* next; char word[]; }* hashtab[HASHTABSIZE]; void* allocassert(void* x) { if (!x) { fprintf(stderr,"out of memory!\n"); exit(1); } return x; } struct node** lookup(char* word) { struct node** x; for (x=&hashtab[hash(word)%HASHTABSIZE]; *x; x=&(*x)->next) if (!strcmp(word,(*x)->word)) break; return x; } char printfbuf[4096]; int comp(const void* a,const void* b) { return (*(struct node**)b)->count - (*(struct node**)a)->count; } int main() { struct node** stab; unsigned long i,j,count=0; char line[8192]; setvbuf(stdout,printfbuf,_IOFBF,sizeof printfbuf); while (fgets(line,sizeof(line),stdin)) { char* x=line; char* y; do { char z; struct node** n; while (isspace(*x)) ++x; y=x; while (*x && !isspace(*x)) ++x; if (x==y) continue; z=*x; *x=0; n=lookup(y); if (!*n) { *n=allocassert(malloc(sizeof(struct node)+strlen(y)+1)); (*n)->count=1; (*n)->next=0; strcpy((*n)->word,y); ++count; } else ++(*n)->count; *x=z; } while (*x); } stab=allocassert(calloc(count,sizeof(stab[0]))); for (i=j=0; inext) { stab[j]=n; ++j; assert(j<=count); } } qsort(stab,count,sizeof(stab[0]),comp); for (i=0; icount,stab[i]->word); return 0; }