#include<iostream>
#include<stdio.h>
using namespace   std;
class CheckString
{
 char key;
public:
 char s[20];
 int len;
 int viewhead;
 int viewend;
 void input();
 void check(const CheckString &substring);
 void kmpcheck(const CheckString &substring);
 void viewnext();
};



void CheckString::input()
{ 
 len=0;
 while((key=getchar())!='\n')
 {
  s[++len]=key;
 }
}


void CheckString::check(const CheckString &substring)
{
 int i=1,j=1;
 while(i<=len)
 {
  if(s[i++]==substring.s[j])
  {
   j++;
   if(j>substring.len)break;
  }
  else
  {
   j=1;
  }
 }
 if(j>substring.len)
 {
  viewhead=i-substring.len;
  viewend=viewhead+substring.len-1;
  cout<<"滿足匹配起始位置:"<<viewhead<<endl;
  cout<<"滿足匹配結束位置:"<<viewend<<endl<<endl;
 }
 else
  cout<<"沒有一樣!!"<<endl<<endl;
}


void CheckString::kmpcheck(const CheckString &substring)
{
 int i=1,j=1;
 int k=0;
 int next[20];
 next[1]=0;
 while(j<substring.len)
  if((k==0)||(substring.s[j]==substring.s[k]))
  {
   j++;
   k++;
   next[j]=k;
  }
  else
   k=next[k];
 cout<<"輸出next[]數組:";
 for(i=1;i<=substring.len;i++)
  cout<<next[i];
 cout<<endl;
 i=1;j=1;
 while((i<=len)&&(j<=substring.len))
  if((j==0)||(s[i]==substring.s[j]))
  {
   i++;
   j++;
  }
  else
   j=next[j];
 if(j>substring.len)
 {
  viewhead=i-substring.len;
  viewend=viewhead+substring.len-1;
  cout<<"滿足匹配起始位置:"<<viewhead<<endl;
  cout<<"滿足匹配結束位置:"<<viewend<<endl<<endl;
 }
 else
  cout<<"沒有一樣!!"<<endl<<endl;
}


void main()
{
 CheckString mainstring;
 CheckString substring;
 cout<<"輸入主串:"<<endl;
 mainstring.input();
 cout<<"輸入子串:"<<endl;
 substring.input();
 cout<<"普通模式匹配算法開始:"<<endl;
 mainstring.check(substring);
 cout<<"KMP模式匹配算法開始:"<<endl;
 mainstring.kmpcheck(substring);
}