#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define N 20

typedef struct node
{  char a;
   int num;
   struct node *next;
}node;

typedef struct nod
{
   char c;
   int num;
   int l;
   int r;
   int p;
}nod;

typedef struct bianma
{  int start;
   char c;
   char s[N];
}bianma;

node * tonji(void);
void print(node *head);
nod *init(node *head);
int mini(nod *head,int i);
bianma *qiuma(nod *head,int i);
void print1(bianma *head,int i);

void main()
{  node *head=NULL;
   nod *head1;
   head=tonji();print(head);
   head1=init(head);

}

node *tonji(void)
{  node *head,*temp,*cursor,*p;
   int i;
   char c;
   char s[]="abcnkjhdsahfsueiofdksjhfaufifhdskljafl";
   if(!s){printf("ERROR!\n");return;}
   head=(node *)malloc(sizeof(node));
   temp=(node *)malloc(sizeof(node));
   temp->a=s[0];
   temp->num=1;
   temp->next=NULL;
   head->next=temp;
   for(i=1;s[i]!=NULL;i++)
   {  for(temp=cursor=head->next;(cursor!=NULL)&&(s[i]!=cursor->a);temp=cursor,cursor=cursor->next);
	  if(cursor==NULL)
	  {
         p=(node *)malloc(sizeof(node));
         p->a=s[i];
	     p->num=1;
	     p->next=NULL;
	     temp->next=p;
	     temp=temp->next;
	  }
	  else
	    cursor->num=cursor->num+1;
   }
   return(head);
}

void print(node *head)
{   node *cursor;
    int i=0;
	if(!head){printf("ERROR!\n");return;}
    for(cursor=head->next;cursor!=NULL;cursor=cursor->next)
    {   printf("%c\t%d;",cursor->a,cursor->num);i=i+cursor->num;}
	printf("\n");
	printf("%d\n",i);
}

nod *init(node *head)
{  int i=0;
   int j=0,k;
   node *cursor;
   nod *head1;
   bianma *ma;
   for(cursor=head->next;cursor!=NULL;cursor=cursor->next)
	   i++;
   j=i*2-1;
   head1=(nod *)malloc(j*sizeof(nod));
   for(i=0,cursor=head->next;cursor!=NULL;i++,cursor=cursor->next)
   {  head1[i].c=cursor->a;
      head1[i].num=cursor->num;
      head1[i].l=head1[i].r=head1[i].p=-1;
   }
   while(i<j)
   {  k=mini(head1,i);
      head1[i].l=k;
	  head1[k].p=i;
	  k=mini(head1,i);
	  head1[i].r=k;
	  head1[k].p=i;
	  head1[i].p=-1;
	  head1[i].num=head1[head1[i].l].num+head1[head1[i].r].num;
	  i++;
   }
   for(k=0;k<i;k++)
   {   printf("%d\t%d;",head1[k].p,head1[k].num);}
   printf("\n");

   printf("%d\n",i);
   ma=qiuma(head1,(i+1)/2);
   print1(ma,(i+1)/2);
   return(head1);
}

int mini(nod *head,int i)
{  int j,k=65535,p;
   for(p=j=0;j<i;j++)
   {  if((head[j].p==-1)&&(k>head[j].num))  {k=head[j].num;p=j;}
   }
   return(p);
}

bianma *qiuma(nod *head,int i)
{  bianma *ma;
   int j,k,p,q;
   ma=(bianma *)malloc(i*sizeof(bianma));
   for(j=0;j<i;j++)
   {   p=head[j].p;q=j;k=N;ma[j].c=head[j].c;
	   for(ma[j].start=N-1;p!=-1;ma[j].start--)
	   {  if(head[p].l==q)
		  ma[j].s[--k]=0;
	      else
			  ma[j].s[--k]=1;
		  q=p;
		  p=head[p].p;
	   }
   }
   return(ma);
}

void print1(bianma *head,int i)
{  int j,k;
   for(j=0;j<i;j++)
   {   printf("%c\t%d\t",head[j].c,head[j].start);
	   for(k=head[j].start+1;k<N;k++)
		   printf("%d",head[j].s[k]);
	   printf("\n");
   }
}