Booth Algorithm in string

Question

I tried solving this problem in SPOJ using Booth Algorithm in O(n) time, but it failed though it worked for all test cases I tried.
Then I did in Brute force way in O(n^2) time, it worked. I have attached the code for both the cases, tell me where I went wrong or is Booth algo a correct approach for this problem?

Isnt the problem, finding the minimum rotation for Lexicographically smallest string

For first approach, Booth Algorithm : http://ideone.com/J5gl5
For second approach, Brute Force : http://ideone.com/ofTeA

Peter de Rivaz · Accepted Answer · 2012-07-26 19:36:35Z

6

Your algorithm gives the wrong answer for string "ABAED", for example.

Your algorithm returns 7 (even though this is longer than the string!).

The correct answer is 0.

(Note this bug may also be present in wherever you found a description of the algorithm! If you look at the history/discussion for the wikipedia article there are a lot of edits fixing bugs - both claiming to fix bugs in the original paper, and to fix bugs in bugfix...)

It seems to work a lot better if you replace:

if( lst[i] < lst[ans+i+1] )

with

if( lst[j] < lst[ans+i+1] )

edited Jul 26, 2012 at 19:36

answered Jul 26, 2012 at 19:23

Peter de Rivaz

33.6k4 gold badges51 silver badges80 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Daniel Fischer Over a year ago

Anyway, the current version in the wikipedia article returns 7 for that input too. en.wikipedia.org/w/… works at least for that.

Peter de Rivaz Over a year ago

Thanks Daniel, any volunteers for raising this as a bug on the discussion page on wikipedia?

sabari Over a year ago

@peter: It worked, but can you explain what is the need for that change and in what cases if( lst[i] < lst[ans+i+1] ) will fail??

Daniel Fischer Over a year ago

@sabari As I understand the algorithm, i is the length of a lexicographically minimal prefix starting at index k which is identical to the substring from index j - i to j - 1. Of course you want to compare the letter after the common substring to check which is lexicographically smaller, the letter at index i is completely unrelated.

Peter de Rivaz Over a year ago

@sabari: I believe it is just a bug in the current wikipedia implementation and my suggested fix should work in all cases (I made a simple test that ran lots of random strings through the algorithm with the proposed change and validated the results against a brute force checker)

|

Collectives™ on Stack Overflow

Booth Algorithm in string

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related