# include <stdio.h>
# include <stdlib.h>
# define MAX 100
int next[100];/*定義全局變量數組next[]*/
typedef struct   
{  
	char *ch;
    int length;
}string;

void creat(string *s) /*創建一個串*/
{
   char c;
   int i;   
   
   for (i=1;(c=getchar())!='\n';i++)
     s->ch[i]=c  ;    /*將輸入的字符序列放入串的字符數組中*/
     s->length=i-1;            /*置串的長度*/
     s->ch[i]= '\0';
}
void print(string *s)    /*輸出串的字符序列*/
{
	 int i;
      for (i=1;s->ch[i]!= '\0';i++)
      printf("%c",s->ch[i]);
      printf("\n");
}
void clearstring(string *s)
{
	if (s->ch) {free(s->ch);s->ch = NULL;}
	s->length = 0;
} 
void Index1(string *s,string *t)/*樸素的模式匹配算法：返回子串在主串中的位置po,若不存在則返回error*/
{
   int i=1,j=1,po; 
   while (i<s->length+1&&j<t->length+1)
   {
	   if (s->ch[i]==t->ch[j]) {i++;j++;}
	   else {i=i-j+2;j=1;}
   }
   if (j>t->length) 
   {
	   po=i-t->length;
	   printf("(樸素)子串的起始位置是k=%d\n",po);	   
   }
   else printf("error\n");
}
void  get_next(string *t)/*next[]的求解*/
{
   int i=1,j=0,k=1;
   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 Index2(string *s,string *t)/*KMP模式匹配算法*/
{
   int i=1,j=1;
   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) 
	   printf("(KMP)子串的起始位置是k=%d\n",i-t->length);
   else printf("error");
}
   
 main()
{
  string *s,*b; 
  int i=1;
  s=(string *)malloc(sizeof(string));
  s->ch=(char *)malloc(100*sizeof(char));
  b=(string *)malloc(sizeof(string));
  b->ch=(char *)malloc(100*sizeof(char));
  printf("輸入主串:");
  creat(s);
  printf("輸入匹配串:");
  creat(b);
  Index1(s,b);
  get_next(b);
  Index2(s,b);
  printf("\n");
}