By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
454,137 Members | 1,001 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 454,137 IT Pros & Developers. It's quick & easy.

C puzzle

P: n/a

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)

Jan 2 '07 #1
Share this Question
Share on Google+
16 Replies


P: n/a
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.
Jan 2 '07 #2

P: n/a
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.

Jan 2 '07 #3

P: n/a

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.

Jan 2 '07 #4

P: n/a

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

Jan 2 '07 #5

P: n/a
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.

Jan 2 '07 #6

P: n/a
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.
Jan 2 '07 #7

P: n/a

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.

Jan 2 '07 #8

P: n/a

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.

Jan 2 '07 #9

P: n/a
"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>
Jan 2 '07 #10

P: n/a
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.

Jan 2 '07 #11

P: n/a

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

Jan 2 '07 #12

P: n/a
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

Jan 2 '07 #13

P: n/a
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.

Jan 2 '07 #14

P: n/a

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 ?

Jan 3 '07 #15

P: n/a
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.
Jan 3 '07 #16

P: n/a
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.

Jan 3 '07 #17

This discussion thread is closed

Replies have been disabled for this discussion.