[In DSqString.h]
bool StrAssign_Sq(DSqString &S,   char *chars)
{  
     int i,j;
     char *c;
	for(i=0,c=chars; *c;   i++,c++);   // c和chars的长度一样了
	if(i==0) { S.str = NULL;    S.length=0; }  //S是空串
	else {//如果S不是空串
		if(!(S.str=(char *)malloc(i*sizeof(char))))  //申请空间
		         {return false;}      //空间申请失败          
		for(j=0;j<i;j++)          //否则，一个一个装填
		S.str[j]=chars[j];
		S.length=i;             
	}
	return true;
}// StrAssign_Sq

[In DSqString.h]
bool StrCopy_Sq(DSqString &S,DSqString T)
{   // 将顺序串T复制到另一个顺序串S中，并返回复制后的顺序串S
	int i;
	if(S.str) free(S.str);                       // 释放S原有空间
	if(!T.length) { S.str=NULL;  S.length=0;  }   // S置为空串
	else {
		if(!(S.str=(char *)malloc(T.length*sizeof(char)))) // 给串S申请空间 
			return false;                 
		for(i=0;i<T.length;i++)                  // 将串T中的字符复制到串S中
		S.str[i]=T.str[i];
		S.length=T.length;                       // 串S的串长为T.length
	} 
	return true;
}// StrCopy_Sq

[In DSqString.h]
int StrCompare_Sq(DSqString S,DSqString T)
{     
	int i=0;
	while(i<S.length&&i<T.length)            // 串S和串T对应字符进行比较
	{
		if(S.str[i]>T.str[i]) return 1;
		else if(S.str[i]<T.str[i]) return -1;
		i++;
	}
	if(i<S.length) return 1;
	else if(i<T.length) return -1;
	return 0;
}// StrCompare_Sq

[In DSqString.h]
bool StrInsert_Sq(DSqString &S,int pos,DSqString T)
    {   // 在顺序串S的第pos个字符之前插入子串T，并返回插入后的顺序串S
     int i;
     if(pos<0||pos>S.length)  return false;    // pos不合理
     if(T.str) {
	   if(!(S.str=(char *)realloc(S.str,(S.length+T.length)*sizeof(char))))   // 给串S增补空间 
			return false;                 
       for(i=S.length-1;i>=pos;i--)            // 为插入串T而腾出位置
        S.str[i+T.length]=S.str[i];
       for(i=0;i<T.length;i++)                  // 插入串T
        S.str[pos+i]=T.str[i];
       S.length=S.length+T.length;             // 串S长度增加T.length
      }
    return true;
}// StrInsert_Sq

[In DSqString.h]
bool StrDelete_Sq(DSqString &S,int pos,int len)
    {  
      int i;
      if(pos<0||pos>S.length-1||len<0||pos+len>S.length)  return false;  // pos和len不合理
      for(i=pos+len;i<S.length;i++)                            // 元素前移，删除子串
        S.str[i-len]=S.str[i];
      S.str=(char *)realloc(S.str,(S.length-len)*sizeof(char)); // 串S空间减少len
      S.length=S.length-len;                                   // 串S长度减少len
      return true;
}// StrDelete_Sq

[In DSqString.h]
void StrReplace_Sq(DSqString &S, DSqString T,DSqString V)
{  
      int  i=0,pos;
      while(Index_Sq(S,T,i,pos))                    // 判断T是否是S的子串
      { StrDelete_Sq(S,pos,T.length);             // 删除子串T
	    StrInsert_Sq(S,pos,V);                    // 插入子串V
		i=i+StrLength_Sq(V);
      }
}// StrReplace_Sq

[In DSqString.h]
void StrTraveres_Sq(DSqString S)
{
	int i;
	for(i=0;i<S.length;i++)
	 cout<<S.str[i];
	cout<<endl;
}// StrTraveres_Sq

[In SLinkString.h]
typedef struct LNode {
	char str;
	struct LNode *next;
}SNode,*SLinkString;

[In SLinkString.h]
typedef struct Chunk{      //可由用户定义的节点大小
      char str[Number]; //一个节点存放Number个字符
      struct Chunk  *next;
}Chunk;               //定义结点类型
typedef struct{
   Chunk  *head, *tail;    //串的头尾指针
   int length;               //串的当前长度
}

[In SLinkString.h]
void StrAssign_L(SLinkString &S, char * chars) {
	SLinkString p, q;
	S = (SLinkString)malloc(sizeof(LNode));
	if (!(*chars)) S->next = NULL;
	else {
		p = S;
		while (*chars) {
			q = (SLinkString)malloc(sizeof(LNode));
			q->str = *chars;
			p->next = q;
			p = q;
			chars++;
		}
		q->next = NULL;
	}
}

[In SLinkString.h]
void StrCopy_L(SLinkString &S, SLinkString T) {
	SLinkString p, q, r;
	while (S->next) {
		p = S;
		S = S->next;
		free(p);
	}
	r = T->next;
	p = S;
	while (r) {
		q = (SLinkString)malloc(sizeof(LNode));
		if (!p) {
			cout << "错误" << endl;
			exit(0);
		}
		q->str = r->str;
		p->next = q;
		p = q;
		r = r->next;
	}
	p->next = NULL;
}

[In SLinkString.h]
int StrLength_L(SLinkString S) {
	int n = 0;
	SLinkString p = S->next;   //传的是指针
	while (p) {
		n++;
		p = p->next;
	}
	return n;
}

[In SLinkString.h]
int StrCompare_L(SLinkString S, SLinkString T) {
   SLinkString p = S->next, q = T->next;
   while (p&&q) {
   	if (p->str > q->str) return 1;
   	else if (p->str < q->str) return -1;
   	p = p->next;
   	q = q->next;
   }
   if (p) return 1;
   else if (q) return -1;
   return 0;
}

[In SLinkString.h]
bool StrConcat_L(SLinkString &S, SLinkString T) {
   SLinkString p, q = S->next, r = T->next;
   while (q->next) q = q->next;
   while (r) {
   	p = (SLinkString)malloc(sizeof(LNode));
   	if (!p) return false;
   	p->str = r->str;
   	q->next = p;
   	q = p;
   	r = r->next;
   }
   q->next = NULL;
   return true;
}

[In SLinkString.h]
bool SubString_L(SLinkString S, SLinkString &Sub, int pos, int len) {
   SLinkString p, q, r;
   int i;
   if (len<0 || len>StrLength_L(S) - pos + 1) return false; //len值不合理
   p = S->next; i = 1;
   while (p&&i < pos) {
   	p = p->next;
   	i++;
   }
   if (i != pos) return false; //pos位置不合理
   while (Sub->next) {
   	q = Sub;
   	Sub = Sub->next;
   	free(q);
   }
   r = Sub;
   for (i = 1; i <= len; i++) {
   	q = (SLinkString)malloc(sizeof(LNode));
   	q->str = p->str;
   	r->next = q;
   	r = q;
   	p = p->next;
   }
   r->next = NULL;
   return true;
}

[In SLinkString.h]
bool Index_L(SLinkString S, SLinkString T, int &pos) {
   int i;
   SLinkString Sub;
   StrAssign_L(Sub, "");   //初始化
   for (i = 1; i < StrLength_L(S) - StrLength_L(T); i++) {
   	SubString_L(S, Sub, i, StrLength_L(T));
   	//cout << Sub->next->str << endl;
   	if (!StrCompare_L(Sub, T)) {
   		//cout << Sub->next->str << endl;
   		pos = i;
   		//cout << i << endl;
   		return true;
   	}
   }
   //cout << "fail" << endl;
   return false;
}

[In SLinkString.h]
bool StrInsert_L(SLinkString &S, int pos, SLinkString T) {
   SLinkString p, q, r, h;
   int i = 0;
   p = S;
   while (p&&i < pos-1) {
   	p = p->next;
   	i++;
   }
   q = p->next;
   if (i != pos-1) return false;
   r = T->next;
   while (r) {
   	h = (SLinkString)malloc(sizeof(LNode));
   	h->str = r->str;
   	p->next = h; h->next = q;
   	p = h; r = r->next;
   }
   return true;
}

[In SLinkString.h]
bool StrDelet_L(SLinkString &S, int pos, int len) {
   SLinkString p = S, r, q;
   if (len < 0 || StrLength_L(S) - pos + 1 < len) return false;
   int i = 0;
   while (p&&i < pos-1) {
   	p = p->next;
   	i++;
   }
   if (i != pos-1) return false;
   q = p->next;
   for (i = 1; i <= len; i++) {
   	r = q;
   	p->next = q->next;
   	q = q->next;
   	free(r);
   }
   return true;
}

[In SLinkString.h]
void StrReplace_L(SLinkString &S, SLinkString T, SLinkString V) {
   int pos = 1;
   while (Index_L(S, T, pos)) {
   	StrDelet_L(S, pos, StrLength_L(T));
   	StrInsert_L(S, pos, V);
   	//pos=pos+StrLength_L(V);
   }
}

[In SLinkString.h]
void StrTraveres_L(SLinkString S) {
   SLinkString p = S->next;
   while (p) {
   	cout << p->str;
   	p = p->next;
   }
   cout << endl;
}

[In SLinkString.h]
void StrTraveres_L(SLinkString S) {
   SLinkString p = S->next;
   while (p) {
   	cout << p->str;
   	p = p->next;
   }
   cout << endl;
}

[In SLinkString.h]
void DestroyString_L(SLinkString &S) {
   SLinkString p, p1;
   p = S;
   while (p)
   {
   	p1 = p;
   	p = p->next;
   	free(p1);
   }
   S = NULL;
}

[In SLinkString.h]
void visualization(SLinkString S, char* filename)
{   int temp;
   FILE *stream;  
   SLinkString p = S->next;
   if( NULL == (stream = fopen(filename, "w")) )  
   {  
      printf("open file error");  exit(0);  
   }  
   fprintf(stream, "digraph\n{\n node [shape = record] \n ");  
   int i=1;
   fprintf(stream, "S[label=\"\头节点\"]; S%d[label=\"<L>%c|<R>*\"];\n  S->S%d:L[label=\"head\"] \n; ",i,p->str,i);
   	i++;
   	p=p->next;
   while(p){
   	fprintf(stream, "S%d[label=\"<L>%c|<R>*\"];\n S%d:R->S%d:L \n; ",i,p->str,i-1,i,p->str);
   	i++;
   	p=p->next;
   	if(p&&!p->next){
   		fprintf(stream, "S%d[label=\"<L>%c|<R>NULL\"];\n S%d:R->S%d:L \n; ",i,p->str,i-1,i,p->str);
   		p=p->next;
   	}
   }
   fprintf(stream, "}"); 
   fclose(stream);  
   system("dot -Tpng show.dot -o show.png");
   system("show.png");
}

# include "stdlib.h"         // 该文件包含malloc()、realloc()和free()等函数
# include "iostream.h"       // 该文件包含标准输入输出流cout和cin
# include "DSqString.h"      // 该文件中包含动态顺序串的相关定义及操作

void get_next(DSqString T,int next[])
{
	int  j=1,k=0;
	next[0]=-1; 
	next[1]=0;
	while(j<T.length)
	{
		if(T.str[j]==T.str[k])
		{
			next[j+1]=k+1;
			j++;  k++;
		}
		else if(k==0)
		{
			next[j+1]=0;
			j++;
		}
		else k=next[k];
	}
}// get_next

bool Index_KMP(DSqString S,DSqString T,int next[],int &pos)
{    // 利用模式串T的next函数求T在主串S中的位置
   int i=0,j=0;                       // i和j分别扫描主串S和子串T
   while(i<S.length&&j<T.length)      
   {  if(j==-1||S.str[i]==T.str[j])   // 继续比较下一个字符
      {  i++;  
  j++;
      }
      else  j=next[j];                 // 模式串向右移动
   }
   if(j==T.length)  { pos=i-T.length; return true;  }
   else return false;
}// Index_KMP