/* -*- C -*-
 *
 * KMP.c -
 *
 * Author : heixia
 * Created On : Sat Mar 22 08:54:54 2008
 *
 */

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

#define MAX 1000

void GetNextval( char *t,int nextval[ ] );
int KMPIndex( char *s,char *t );

int main( ){
     char s[ 50 ] = "abcaabbabcabaacbacba";
     char t[ 10 ] = "abcabaa";
     int next[ 10 ];

     int i = 0;

     i = KMPIndex( s,t );

     if( i != -1 )
          printf("The matched position is: %d\n",i);
     else
          printf( "Can't be matched.\n" );
}

void GetNextval( char *t,int nextval[ ] ){
     int j = 0,k = -1,len = strlen( t );
     nextval[ 0 ] = -1;

     
     while( j < len ){
          if( k == -1 || t[ j ] == t[ k ] ){
               j ++;
               k ++;
               if( t[ j ] != t[ k ] )
                    nextval[ j ] = k;
               else
                    nextval[ j ] = nextval[ k ];
          }
          else
               k = nextval[ k ];
     }
}

int KMPIndex( char *s,char *t ){
     int next[ MAX ],i = 0,j = 0,v;

     int len1 = strlen( s ),len2 = strlen( t );
     
     GetNextval( t,next );

     while( i < len1 && j < len2 ){
          if( j == -1 || s[ i ] == t[ j ] ){
               i ++;
               j ++;
          }
          else
               j = next[ j ];
     }

     if( j >= len2 )
          v = i- len2;
     else
          v = -1;

     return v;
}