454,137 Members | 1,001 Online
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
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 #include 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 ) 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

 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

 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 whethers2 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. 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 themood hits I will publish a solution later, after the OP's date forpassing in his homework has been passed. Although the solutionusing 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