KMP算法，实现串替换

#include "stdafx.h"
#include "iostream.h"
#include "stdio.h"
#define  Null 0

//定义串的链存储结构
typedef struct Chuck{
char ch;
struct Chuck *next;
}Chuck;

typedef struct {
Chuck *head,*tail;
int length;
}Hstring;

void init_Hstring(Hstring &T);
//删除pos结点后面length长度的字符串
void delete_pos(Hstring &S,Chuck *pos,int length);
//pos结点后面插入length长度的字符串
void insert_pos(Hstring &S,Chuck *pos,int length);

//模式匹配
int  Index_KMP(Hstring &S,Hstring &T,int pos);
void get_next(Hstring &T,int next[]);

void init_Hstring(Hstring &T){
 T.head=T.tail =new Chuck;
 T.head->next =Null;
 T.length =0;
}

void delete_pos(Hstring &S,Chuck *pos,int length){
  Chuck *p,*q;
  p=S.head ;
  while(p->next !=pos)
   p=p->next;
  q=p;
  for(int i=0;i<length;i++)
   p=p->next ;

  S.length-=length;
}

int  Index_KMP(Hstring &S,Hstring &T,int pos){
 int i=pos,j=1;
 int next[51];

 get_next(T,next);
 while(i<=S.length&&j<=T.length){
  if(j==0||S.ch[i]==T.ch[j]){
  ++i;++j;
  }
  else
  j=next[j];
 }
 if(j>T.length) return i-T.length;
 else return 0;
}

void get_next(Hstring &T,int next[]){
 int i=1,j=0;
 next[1]=0;
 while(i<T.length){
  if(j==0||T.ch[i]==T.ch[j]){
   ++i;++j;next[i]=j;
   }
  else
   j=next[j];
 }
}

int main(int argc, char* argv[])
{
 Hstring S,T;
 char *p="Please Input ";
 char *q="Error: S.length<T.length";
 int pos=1,tag;
 init_Hstring(S);
 init_Hstring(T);
 cout<<p<<"S:"<<endl; //endl,强制输出
 for(int k=1;(S.ch[k]=getchar())!='\n';k++);
 S.ch[k]='\0';
 S.length=k-1;
 cout<<p<<"T:"<<endl;
 for(k=1;(T.ch[k]=getchar())!='\n';k++);
 T.ch[k]='\0';
 T.length=k-1;
 
 if(S.length>=T.length)
  while(pos<=S.length-T.length+1){
   tag=Index_KMP(S,T,pos);
   if(!tag)
    break;
   else
   {delete_pos(S,tag,T.length);
   pos=1;}
  }
  
 else
 {cout<<q<<endl;return 0;}

 //输出结果
 for(k=1;S.ch[k]!='\0';k++)
 cout<<S.ch[k]<<" ";
 cout<<endl;
 return 0;
}