#include<stdio.h>
//#include<stdlib.h>
typedef struct {
    char *ch;
    int length;
}hstring;
/*author.jiang.2010.5.16*/
void init(hstring *t){
    (*t).ch=NULL;
    (*t).length=0;
}

void strassign(hstring *t,char *chars){
    int i,j;
    char *c;
    if(t->ch) free(t->ch);
    for(i=0,c=chars;*c;i++,c++);
    if(!i){
        t->ch=NULL;
        t->length=0;
    }
    else{
        t->ch=(char*)malloc(sizeof(char)*i);
        if(!t->ch)
            exit(0);        
        for(j=0;j<i;j++)
        (*t).ch[j]=chars[j];
        t->length=i;
    }
}


void strcopy(hstring *t,hstring s){
    int i;
    if(t->ch) free(t->ch);
    t->ch=(char*)malloc(sizeof(char)*s.length);
    for(i=0;i<s.length;i++)
        t->ch[i]=s.ch[i];
    t->length=s.length;
}
int strempty(hstring s){
    if(s.ch==NULL&&s.length==0)
        return 1;
    else
        return 0;
}
int strcompare(hstring s,hstring t){
    int i;
    for(i=0;i<s.length&&i<t.length;i++)
        if(s.ch[i]!=t.ch[i])
            return s.ch[i]-t.ch[i];
        return s.length-t.length;
}
int strlength(hstring s){
    return s.length;
}
void clearstring(hstring *s){
    if(s->ch)
    {free(s->ch);s->ch=NULL;}
    s->length=0;
}
void concat(hstring *t,hstring s1,hstring s2){
    int i;
    if(t->ch)
        free(t->ch);
    t->ch=(char*)malloc(sizeof(char)*(s1.length+s2.length));
    if(!t->ch)
        exit(0);
    for(i=0;i<s1.length;i++)
        t->ch[i]=s1.ch[i];
    for(i=0;i<s2.length;i++)
        t->ch[i+s1.length]=s2.ch[i];
    t->length=s1.length+s2.length;

}
void substring(hstring *sub,hstring s,int pos,int len){
    int i;
    if(sub->ch)
        free(sub->ch);
    if(pos<1||pos>s.length||len<0||len>s.length-pos+1)
        return;
    sub->ch=(char*)malloc(sizeof(char)*len);
    if(!sub->ch)
        exit(0);
    for(i=pos-1;i<pos+len-1;i++)
        sub->ch[i-pos+1]=s.ch[i];
    sub->length=len;
}

int index(hstring s,hstring t,int pos){
    int m,n,i;
    hstring sub;
    init(&sub);
   
   
    if(pos>0){
        n=s.length;m=t.length;i=pos;
        while(i<=n-m+1){
            substring(&sub,s,i,m);
            if(strcompare(sub,t)!=0)
                i++;
            else
                return i;
        }
    }
        

    return 0;
}
void strinsert(hstring *s,int pos,hstring t){
    int i;
    if(pos<1||pos>s->length+1)
        return;
    if(t.length){
    s->ch=(char*)realloc(s->ch,sizeof(char)*(s->length+t.length));
    if(!s->ch)
        exit(0);
    for(i=s->length-1;i>=pos-1;i--)
        s->ch[t.length+i]=s->ch[i];
    for(i=0;i<t.length;i++)
        s->ch[i+pos-1]=t.ch[i];
    s->length+=t.length;
    }
}
void strdelete(hstring *s,int pos ,int len){
    int i;
    if(pos<1||pos>s->length-len+1)
        return;
    for(i=pos+len-1;i<s->length;i++)
        s->ch[i-len]=s->ch[i];
    s->length-=len;
    s->ch=(char*)realloc(s->ch,sizeof(char)*s->length);
}
void replace(hstring *s,hstring t,hstring v){
    int i=1;
    if(strempty(t))
        return;
    do{
        i=index(*s,t,i);
        if(i>0){
            strdelete(s,i,t.length);
            strinsert(s,i,v);
            i+=v.length;
        }
    }while(i);
}



void strprint(hstring t){
    int i;
    for(i=0;i<t.length;i++)
        printf("%c",t.ch[i]);
    printf("\n");
}

main()
{   int i;
    hstring t,s1,s2,s3,s4,s5;
    char c,*a="aa",*b="**",*p="112233",*q="aabbccaa";
    init(&s1);
    init(&s2);
    init(&s3);
    init(&s4);
    init(&s5);
    init(&t);

    strassign(&s1,p);
    printf("s1:");
    strprint(s1);
    printf("s1/length:%d/empty(1 :Yes):%d\n",strlength(s1),strempty(s1));
    strcopy(&s3,s1);
    printf("copy/s1->s3:");
    strprint(s3);
    strassign(&s2,q);
    printf("s2:");
    strprint(s2);
    i=strcompare(s1,s2);
    if(i<0) c='<';
    else if(i==0) c='=';
    else c='>';
    printf("s1%cs2\n",c);
    concat(&t,s1,s2);
    printf("concat/s1+s2->t:");
    strprint(t);
    strassign(&s4,a);
    printf("s4:");
    strprint(s4);
    i=index(s2,s4,1);printf("index/s2/s4/1:%d\n",i);
    i=index(s2,s4,3);printf("index/s2/s4/3:%d\n",i);
    strinsert(&s1,2,s4);
    printf("insert/s1/2/s4:");
    strprint(s1);
    strdelete(&s1,2,3);
    printf("delete/s1/2/3:");
    strprint(s1);
    strassign(&s5,b);
    printf("s5:");
    strprint(s5);
    replace(&t,s4,s5);
    printf("replace/s4/s5:");
    strprint(t);
    clearstring(&s1);
    printf("clear/s1:");
    strprint(s1);
    printf("s1/length:%d/empty(1 :Yes):%d\n",strlength(s1),strempty(s1));
}