struct State {

   int length, suf, pos;

   char terminal;

};



typedef struct State STATE;



int state_counter;





/* Creates and returns a clone of state p. */

int COPY ( int p , STATE states[] , int trans[ XSIZE ][ ASIZE ])

{

 int r;

 

 r = state_counter++;

 memcpy( trans[ r ] , trans[ p ] , ASIZE * sizeof( int ));

 states[ r ].suf = states[ p ].suf;

 states[ r ].pos = states[ p ].pos;

 return (r);

}





/* Creates the suffix automation for the reverse of the word x and */

/*  returns its initial state.                              */

int SUFF( char *x, int m, STATE states[], int trans[ XSIZE ][ ASIZE ])

{

 int i, art, init, last, p, q, r;

 char a;

 

 art = state_counter++;

 init = state_counter++;

 states[ init ].suf = art;

 last = init;

 for ( i = m - 1; i >= 0; --i) {

    a = x[ i ];

   p = last;

   q = state_counter++;

   states[ q ].length = states[ p ].length + 1;

   states[ q ].pos = states[ p ].pos + 1;

   while ( p != init && trans[ p ][ a ] == 0 ) {

      trans[ p ][ a ] = q;

      p = states[ p ].suf;

   }

   if ( trans[ p ][ a ] == 0 ) {

      trans[ init ][ a ] = q;

      states[ q ].suf = init;

   }

   else

     if ( states[ p ].length + 1 == states[ trans[ p ][ a ] ].length)

        states[ q ].suf = trans[ p ][ a ];

     else {

 r = COPY( trans[ p ][ a ], states, trans );

 states[ r ].length = states[ p ].length + 1;

 states[ trans[ p ][ a ] ].suf = r;

 states[ q ].suf = r;

 while (p!=art && states[trans[p][a]].length >= states[r].length)

 {

    trans[ p ][ a ] = r;

   p = states[ p ].suf;

 }

    }

   last = q;

 }

 states[ last ].terminal = 1;

 p = last;

 while ( p != init ) {

    p = states[ p ].suf;

   states[ p ].terminal = 1;

 }

 return ( init );

}





/* Reverse Factor Algorithm. */

int RF( char *y, char *x, int n, int m)

{

 int i, j, shift, period, init, state, state_aux;

 STATE states[ 2 * XSIZE + 2 ];

 int trans[ XSIZE ][ ASIZE ];

 

 /* Preprocessing */

 memset( trans, 0, 2 * ( m + 2 ) * ASIZE * sizeof ( int ) );

 memset( states, 0, 2 * ( m + 2 ) * sizeof( STATE ) );

 state_counter = 1;

 i = 0; period = m;

 

 /* Construction of the minimal suffix of the reverse of x */

 init = SUFF( x , m , states , trans );

 

 /* Searching */

 while ( i <= n - m ) {

    j = m - 1;

   state = init;

   shift = m;

   while ( ( state_aux = trans[ state ][ y[ i+j ] ]) != 0) {

      state = state_aux;

      if ( states[ state ].terminal) {

         period = shift;

         shift = j;

      }

      j--;

   }

   if ( j < 0 ) {

      OUTPUT ( i );

      shift = period;

   }

   i += shift;

  }

}