#include<stdio.h>
#include<stdlib.h>
#include<iostream>

using namespace std;

#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define N 100
#define MAXSIZE 100

typedef int Status;
typedef char ElemType;

typedef struct
{
    char *ch;//若是非空串，则按串长分配存储区，否则ch为NULL 
    int length;//串的当前长度 
 } HString;
 
 //初始化一个串
 Status InitString(HString &s)
 {
     
     s.ch=new ElemType[MAXSIZE];//初始化，给串赋以动态空间 
     if(!s.ch) exit(OVERFLOW);
     s.length=0;
     return OK;
  } 
 
 //创建一个串（给字符串赋值） 
 Status StrAssign(HString &s,int len)
 {
    char e;
    for(int i=1;i<=len;i++)
    {
     cin>>e;
    s.ch[i]=e; //给串赋值 
    }
    s.length=len;//让串长为len 
     return OK;
  }
   

   //打印串
   Status Display(HString &s)
   {
       for(int i=1;i<=s.length;i++)
       {
           printf("%c",s.ch[i]);//展示串中元素 
       }
       printf("\n");
       return OK;
    } 
    
 //BF算法
 int Index_BF(HString S,HString T,int &pos)
 {
     int i=1,j=1;
     while(i<=S.length&&j<=T.length)//当i,j小于串长时，比较主串和模式串 
     {
         if(S.ch[i]==T.ch[j])
         {
         i++;//比较后继字符串 
        j++;
         }
    else
     {
         i=i-j+2;//i指针回溯 
         j=1;//并使数组下标为第一个元素下标 
       }
     }
     if(j>T.length) 
     {
     
      pos=i-T.length;//匹配成功 
      return i-T.length;
     }
     else return 0;//匹配失败 
  } 
  
  //KMP算法
  int Index_KMP(HString S,HString T,int &x,int next[])
  {
      int i=1,j=1;
      while(i<=S.length&&j<=T.length)
      {
          if(S.ch[i]==T.ch[j]||j==0)
          {
              ++i;//比较后继字符串 
              ++j;
          }
          else
          {
              j=next[j];//模式串向右移动 
          }
      }
      if(j>T.length) 
      {
          //匹配成功
          x=i-T.length;
      return i-T.length;
      }
else return 0;//匹配失败 
   } 
   
 //next函数
 void get_next(HString T,int next[])
 {
     next[1]=0;
     int k,j;
     k=0;j=1;
     while(j<T.length)
     {
         if(k==0||T.ch[j]==T.ch[k])
         {
             ++j;++k;
             next[j]=k;
         }
         else k=next[k];
     }
  } 
  
  //nextval函数
  void get_nextval(HString T,int nextval[])
  {
      nextval[0]=0;
      int k=0,j=1;
      while(j<T.length)
      {
          if(k==0||T.ch[k]==T.ch[j])
          {
              ++j;++k;
              if(T.ch[k]==T.ch[j])
              nextval[j]=nextval[k];
              else nextval[j]=k;
          }
          else k=nextval[k];
      }
   }
 int main()
 {
     char e;
     int n,m,x,pos,y;
     int next[N],nextval[N];
     HString S,T;
     InitString(S);
     InitString(T);
     
     printf("串长为：");
     scanf("%d",&n);
     printf("请输入字符串S:");
     StrAssign(S,n);
     printf("此时串S中元素为:");
     Display(S);
     
     printf("串长为：");
     scanf("%d",&m);
     printf("请输入字符串T:");
     StrAssign(T,m);
     printf("此时串T中元素为:");
     Display(T);
     
    Index_BF(S,T,pos);
     printf("BF 模式T在主串S中,第%d个字符开始第一次匹配\n",pos);
      
     get_next(T,next);
     Index_KMP(S,T,x,next);
     printf("KMP 模式串T在主串S中,第%d个字符开始第一次匹配\n",x);
     
     //get_next(T,nextval);
     get_nextval(T,nextval);
     Index_KMP(S,T,y,nextval);
     printf("KMP 模式串T在主串S中,第%d个字符开始第一次匹配\n",y);
  }