deepak wrote:

Given a string s1 and a string s2, write a snippet to say whether s2

is a

rotation of s1 using only one call to strstr routine?

(eg given s1 = ABCD and s2 = CDAB, return true,

given s1 = ABCD, and s2 = ACBD , return false)

/* parody of computer science homework

given

a[0]...a[n-1]

b[0]...b[n-1]

evaluate

n==0 || exist 0<=k<n (forall 0<=i<n (a[i] == b[(i+k) mod n]) )

*/

#include <string.h>

#include <assert.h>

void

assert_invariant( const char *a, const char *b, size_t n, size_t k,

size_t i, size_t j )

{

size_t t = 0;

assert( j == (i+k)%n );

for ( t=0; t < i; t++ )

assert( a[t] == b[(t+k)%n] );

}

/* return true iff forall 0<=i<n (a[i] == b[(i+k)%n]) */

int

is_rot_at_offset( const char *a, const char *b, size_t n, size_t k )

{

size_t i =0, j = 0;

assert( 0 <= k && k < n ); /*precondition*/

j = i+k;

assert_invariant( a, b, n, k, i, j );

while ( i<n && a[i] == b[j] )

{

j++;

if ( j >= n )

j = 0;

i++;

assert_invariant( a, b, n, k, i, j );

}

assert_invariant( a, b, n, k, i, j );

assert( 0 <= i && i <= n );

assert( i==n || a[i] != b[j] );

return i == n;

}

/* return true iff n == 0 || exist 0<=k<n (forall 0<=i<n (a[i] ==

b[(i+k)%n]) )*/

int

is_rot( const char *a, const char *b )

{

size_t k =0;

size_t n =0;

if ( a == NULL )

return b == NULL;

assert( a != NULL );

if ( b == NULL )

return 0;

assert( a != NULL );

assert( b != NULL );

n = strlen(a);

if ( n != strlen(b) )

return 0;

assert( n == strlen(a) && n == strlen(b) );

while ( k < n && ! is_rot_at_offset( a, b, n, k ) )

k++;

return n == 0 || k != n;

}

void

test_is_rot()

{

assert( is_rot(NULL,NULL) );

assert( !is_rot(NULL,"") );

assert( !is_rot("",NULL) );

assert( is_rot("","") );

assert( !is_rot("","a") );

assert( !is_rot("a","") );

assert( is_rot("a","a") );

assert( is_rot("ab","ab") );

assert( is_rot("ba","ab") );

assert( is_rot("ab","ba") );

assert( !is_rot("abc","ba") );

assert( !is_rot("ba","abc") );

assert( is_rot("abc","cab") );

assert( is_rot("abc","bca") );

assert( !is_rot("ba","abc") );

assert( is_rot("abcd","cdab") );

assert( is_rot("cdab","abcd") );

}

int

main()

{

test_is_rot();

return 0;

}