using system;

namespace kmp
{
 /// <summary>
 /// summary description for class1.
 /// </summary>
 class class1
 {
  /// <summary>
  /// the main entry point for the application.
  /// </summary>
  static int[] next=new int[20];
  static int count=0;
  static int kmp(char[] a, char[] b, int pos)
  {
   int i=pos, j=0;
   int lena=a.length,lenb=b.length;
   count=0;
   while((i<=lena-1)&&(j<=lenb-1))
   {
    if(a[i]==b[j])
    {++i;++j;}
    else
    {i=i-j+1; j=0;}
    count++;
   }
   if(j>lenb-1)
    return i-lenb;
   else
    return 0;
  }
  [stathread]
  static void main(string[] args)
  {
   //
   // todo: add code to start application here
   //
   int pos=0,reval;
   console.writeline("input string1");
   string s1=console.readline();
   console.writeline("input string2");
   string s2=console.readline();
   char[] p1=s1.tochararray();
   char[] p2=s2.tochararray();
   console.writeline("lena={0},lenb={1}",p1.length,p2.length);
   reval=kmp(p1,p2,pos);
   console.writeline("====not kmp ====");
   console.writeline("value={0},count={1}",reval,count);
   get_next(p2,next);
   reval=index_kmp(p1,p2,pos);
   console.writeline("====this is kmp ====");
   console.writeline("value={0},count={1}",reval,count);
   get_goodnext(p2,next);
   reval=index_kmp(p1,p2,pos);
   console.writeline("====this is good kmp ====");
   console.writeline("value={0},count={1}",reval,count);
   console.readline();
  }
  static int index_kmp(char[] a,char[] b, int pos)
  {
   int i=pos, j=0;
   int lena=a.length,lenb=b.length;
   count=0;
   while((i<=lena-1)&&(j<=lenb-1))
   {
    if(j==0||a[i]==b[j])
    {++i;++j;}
    else
    {j=next[j];}
    count++;
   }
   if(j>lenb-1)
    return i-lenb;
   else
    return 0;
  }
  static void get_next(char[] a,int[] next)
  {
   int i=1,j=0;
   next[0]=0;
   while(i<=a.length-2)
   {
    if(j==0||a[i]==a[j])
    {++i;++j;next[i]=j;}
    else
    {j=next[j];}
   }
  }
  static void get_goodnext(char[] a,int[] next)
  {
   int i=1,j=0;
   next[0]=0;
   while(i<=a.length-2)
   {
    ++i;++j;
    if(j==0||a[i]==a[j])
    {
     if(a[i]!=a[j])
     {
      next[i]=j;
     }
     else
     {
      next[i]=next[j];
     }
    }
    else
    {j=next[j];}
   }
  }
 }
}