#define  TRUE         1
#define  FALSE        0
#define  OK           1
#define  ERROR        0
#define  IBFEASIBLE  -1
#define  OVERFLOW    -2  
typedef  int   Status;

#define  errInt   -999
#define  MAXSTRLEN  254

// 串的定长顺序表示
//typedef  unsigned char  SStr[MAXSTRLEN+1];  // 0 单元存放串的长度
typedef  unsigned char  *SStr;  // 串长<=255，0号单元存放串的长度，需动态分配空间

typedef SStr  String;
SStr errStr;

int random1i(int x) {  
   if (x<0) return 0;
   else return (int)rand() % x;
}

int random2i(int x, int y) { // 返回一个值大于等于x, 小于y 的非负随机数,
   if (x>=y) return x;
   else return (int)rand() % (y-x) + x;
}

String StrFree(String S) {
   if (S) free(S);   
   return NULL;
}

String allocStr(int len) {  
   String S;
   if (len>MAXSTRLEN) len = MAXSTRLEN;   
   if (!(S = (String)calloc(len+2, sizeof(char)))) exit(OVERFLOW);
   S[0] = len;   
   return S;
}

String StrNew(char *cs) {  // 返回由C串cs构造的短串
   int cslen;   char *c;
   for (cslen=0, c=cs; *c++; ++cslen);         // 求cs的长度i
   String S = allocStr(cslen);                  // 按cs长度分配存储空间
   memcpy(S+1, cs, (int)S[0]);                 // 复制cs前cslen个字符为串值
   S[1+S[0]] = '\0';   return S;               // 置结束符，返回S
}


String StrAssign(String S, int pos, char *cs) {
   
   int len, newlen, oldlen;   char *c;
   if (!S || pos<1 || pos>1+S[0]) return S;    
   for (len=0, c=cs; *c++; ++len);             
   if (0==len) return S;                       
   if ((newlen = pos+len-1) > S[0]) {          
      if (newlen>MAXSTRLEN) newlen = MAXSTRLEN;    
      S[0] = newlen;    len = newlen - pos +1;      
      if (!(S = (String)realloc(S, (newlen+2)*sizeof(char)))) exit(OVERFLOW); 
      S[newlen+1] = '\0';                    
   } 
   memcpy(S+pos, cs, len);                  
   return S;                                  
} 
                          
String StrCopy(String S) {       
   if (!S) return NULL;       
   String T;
   if (!(T = (String)malloc((2+S[0])*sizeof(char)))) exit(OVERFLOW);      
      memcpy(T, S, 2+S[0]);                     
   return T;
}

String CreateRandomStr(int length) {
   String S;
   int len = random2i(length/2, length);
   if (!(S = (String)malloc((len+2)*sizeof(char)))) exit(OVERFLOW);
   S[0] = len;
   for (int i=1; i<=len; i++) S[i] = 'A'+random1i(26); 
   S[len+1] = '\0';   return S;        
}

int StrLen(String S) {
   if (S) return S[0];
   else return 0;        
}   

int StrCmp1(String S, String T) {
   if (!S || !T) return errInt;                 
   for (int i=1; i<=S[0]; i++)                  
      if (S[i] != T[i]) return (int)S[i]-T[i];
   return 0;
}


int StrCmp(String S, String T) {  
   if (!S || !T) return errInt;                
   for (S++, T++; *S && *S == *T; S++, T++);   
   return (int)*S-*T;                          
}      

String StrConcat(String S1, String S2) {     
   String T;  int i;
   if (!S1 || !S2) return  NULL;                     
   if (S1[0]+S2[0] <= MAXSTRLEN) {                   
      T = allocStr(S1[0]+S2[0]);                      
      //for (i=1; i<=S1[0]; i++) T[i] = S1[i];          
      memmove(T+1, S1+1, (int)S1[0]);                  
      //for (i=1; i<=S2[0]; i++) T[i+S1[0]] = S2[i];    
      memmove(T+(int)S1[0]+1, S2+1, (int)S2[0]);        
      T[0] = S1[0]+S2[0];
   } else if (S1[0] < MAXSTRLEN) {                    
      T = allocStr(MAXSTRLEN);
      //for (i=1; i<=S1[0]; i++) T[i] = S1[i];
      memmove(T+1, S1+1, (int)S1[0]);             
      //for (i=S1[0]+1; i<=MAXSTRLEN; i++) T[i] = S2[i-S1[0]];
      memmove(T+(int)S1[0]+1, S2+1, MAXSTRLEN-S1[0]);             
      T[0] = MAXSTRLEN;
   } else {                                           
      T = allocStr(MAXSTRLEN);
      //for (i=0; i<=MAXSTRLEN; i++) T[i] = S1[i];
      memmove(T, S1, (int)S1[0]+1);             
   }
   T[T[0]+1] = '\0';   return T;
} 

String StrSub(String S, int pos, int len) { 
   if (!S || pos<1 || pos>S[0] || len<0 || len>S[0]-pos+1)
      return NULL;
   String Sub = allocStr(len);
   //for (int i=1; i<=len; i++) Sub[i] = S[pos+i-1];
   memcpy(Sub+1, S+pos, len);             
   Sub[0] = len;   Sub[len+1] = '\0';
   return Sub;
}

Status StrRange(String S, int a, int b) { 
   if (!S || a<1 || a>b || b>S[0]) return ERROR;  
   S[0] = b-a+1;                                  
   memcpy(S+1, S+a, (int)S[0]);                
   S[1+S[0]] = '\0';                            
   return OK;
}

int Index(String S, String T, int pos) {  
    
    int i = pos, j = 1;
    while (i <= S[0] && j <= T[0])
        if (S[i] == T[j]) { ++i;   ++j; }   
        else { i = i-j+2;   j = 1; }       
    if (j > T[0]) return  i-T[0];
    else return 0;
}
void StrPrintf(String S) {   
  printf("\"%s\"\n", &S[1]);
}