C puzzle

[deepak]

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)

[Richard Heathfield]

deepak said:

>
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?

Surely that's your job?

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[loic-dev]

Hello,

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)

This is not really complicated. A possible algorithm consists to:

1) Find n, such that s2[n] == s1[0]
2) Build a temporary string y which is s2 rotated of n positions.
3) Compare s1 and y.

Cheers,
Loic.

[junky_fellow]

lo******@gmx.net wrote:

Hello,

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)

This is not really complicated. A possible algorithm consists to:

1) Find n, such that s2[n] == s1[0]
2) Build a temporary string y which is s2 rotated of n positions.
3) Compare s1 and y.

This may not work if
s1 = ABCADE and s2 = CADEAB
s2[n] = A, where n = 1. temporary string y = ADEABC.
s1 compares not equal to y.
I mean to say your algorithm will fail, if there is more than one s1[0]
in string s2.

[cloverman]

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;
}

[loic-dev]

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)

This is not really complicated. A possible algorithm consists to:

1) Find n, such that s2[n] == s1[0]
2) Build a temporary string y which is s2 rotated of n positions.
3) Compare s1 and y.

This may not work if
s1 = ABCADE and s2 = CADEAB
s2[n] = A, where n = 1. temporary string y = ADEABC.
s1 compares not equal to y.
I mean to say your algorithm will fail, if there is more than one s1[0]
in string s2.

Absolutely true. But do you really want me to remove all the fun of
this homework? ;-)

Cheers,
Loic.

[Christopher Benson-Manica]

deepak <de*********@gmail.comwrote:

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?

It's a snap - write your own strstr routine and then you can call it
as many times as you want...

--
C. Benson Manica | I *should* know what I'm talking about - if I
cbmanica(at)gmail.com | don't, I need to know. Flames welcome.

[junky_fellow]

lo******@gmx.net 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)
>
This is not really complicated. A possible algorithm consists to:
>
1) Find n, such that s2[n] == s1[0]
2) Build a temporary string y which is s2 rotated of n positions.
3) Compare s1 and y.
>

This may not work if
s1 = ABCADE and s2 = CADEAB
s2[n] = A, where n = 1. temporary string y = ADEABC.
s1 compares not equal to y.
I mean to say your algorithm will fail, if there is more than one s1[0]
in string s2.

Absolutely true. But do you really want me to remove all the fun of
this homework? ;-)

I think you probably intended to repeat those three steps in a loop
until the end of s2 is reached.

[junky_fellow]

lo******@gmx.net 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)
>
This is not really complicated. A possible algorithm consists to:
>
1) Find n, such that s2[n] == s1[0]
2) Build a temporary string y which is s2 rotated of n positions.
3) Compare s1 and y.
>

This may not work if
s1 = ABCADE and s2 = CADEAB
s2[n] = A, where n = 1. temporary string y = ADEABC.
s1 compares not equal to y.
I mean to say your algorithm will fail, if there is more than one s1[0]
in string s2.

Absolutely true. But do you really want me to remove all the fun of
this homework? ;-)

I think you probably intended to repeat those three steps in a loop
until the end of s2 is reached.

[CBFalconer]

"ju**********@yahoo.co.in" wrote:

lo******@gmx.net 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)

This is not really complicated. A possible algorithm consists to:

1) Find n, such that s2[n] == s1[0]
2) Build a temporary string y which is s2 rotated of n positions.
3) Compare s1 and y.

This may not work if
s1 = ABCADE and s2 = CADEAB
s2[n] = A, where n = 1. temporary string y = ADEABC.
s1 compares not equal to y.
I mean to say your algorithm will fail, if there is more than one s1[0]
in string s2.

Much simpler will work. No calls to strstr are needed. If the
mood hits I will publish a solution later, after the OP's date for
passing in his homework has been passed. Although the solution
using a single strstr call is fairly elegant and quite efficient.

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>

[loic-dev]

Hi,

Much simpler will work. No calls to strstr are needed. If the
mood hits I will publish a solution later, after the OP's date for
passing in his homework has been passed. Although the solution
using a single strstr call is fairly elegant and quite efficient.

I agree that the solution of /strstr()/ is fairly elegant.

Cheers,
Loic.

[dspfun]

lo******@gmx.net skrev:

Hi,

Much simpler will work. No calls to strstr are needed. If the
mood hits I will publish a solution later, after the OP's date for
passing in his homework has been passed. Although the solution
using a single strstr call is fairly elegant and quite efficient.

I agree that the solution of /strstr()/ is fairly elegant.

Cheers,
Loic.

Append str1 to itself and do a strstr for str2

[Randy Howard]

On Tue, 2 Jan 2007 10:58:42 -0600, dspfun wrote
(in article <11**********************@h40g2000cwb.googlegroups .com>):

>
lo******@gmx.net skrev:

>Hi,

>>Much simpler will work. No calls to strstr are needed. If the
mood hits I will publish a solution later, after the OP's date for
passing in his homework has been passed. Although the solution
using a single strstr call is fairly elegant and quite efficient.

I agree that the solution of /strstr()/ is fairly elegant.

Cheers,
Loic.

Append str1 to itself and do a strstr for str2

*sigh*

--
Randy Howard (2reply remove FOOBAR)
"The power of accurate observation is called cynicism by those
who have not got it." - George Bernard Shaw

[loic-dev]

Good evening,

Much simpler will work. No calls to strstr are needed. If the
mood hits I will publish a solution later, after the OP's date for
passing in his homework has been passed. Although the solution
using a single strstr call is fairly elegant and quite efficient.

I agree that the solution of /strstr()/ is fairly elegant.

Cheers,
Loic.

Append str1 to itself and do a strstr for str2

close, but not yet 100% correct.

Cheers,
Loic.

[junky_fellow]

lo******@gmx.net wrote:

Good evening,

Much simpler will work. No calls to strstr are needed. If the
mood hits I will publish a solution later, after the OP's date for
passing in his homework has been passed. Although the solution
using a single strstr call is fairly elegant and quite efficient.
>
I agree that the solution of /strstr()/ is fairly elegant.
>
Cheers,
Loic.

Append str1 to itself and do a strstr for str2

close, but not yet 100% correct.

Do you mean to say that the size of s1 and s2 should also be checked ?
str1 = AAA
str2 = AAAA
append str1 to itself to get str3, str3 = AAAAAA
strstr() for str2 in str3 will be a success.

Or is there any other corner case that you have in your mind ?

[Richard Heathfield]

Randy Howard said:

On Tue, 2 Jan 2007 10:58:42 -0600, dspfun wrote:

>>
Append str1 to itself and do a strstr for str2

*sigh*

Whilst it's true that two O(n) operations still give you O(n), that doesn't
make it any less painful to watch, does it?

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[loic-dev]

Hello,

Append str1 to itself and do a strstr for str2

close, but not yet 100% correct.

Do you mean to say that the size of s1 and s2 should also be checked ?

yes, exactly.

Or is there any other corner case that you have in your mind ?

The proof that there is no other corner case if left as an exercice to
the reader.

Cheers,
Loic.