c - 字符串中的 Booth 算法

Question

我尝试解决这个 problem在 SPOJ 中使用 Booth Algorithm在 O(n) 时间内，但它失败了，尽管它适用于我尝试过的所有测试用例。
然后我在 O(n^2) 时间内以蛮力方式做了，它起作用了。我附上了这两种情况的代码，请告诉我哪里出错了，或者 Booth 算法是解决这个问题的正确方法吗？

这不是问题，找到字典序最小字符串的最小旋转

对于第一种方法，Booth 算法:http://ideone.com/J5gl5
对于第二种方法，蛮力:http://ideone.com/ofTeA

Answer 1

例如，您的算法对字符串“ABAED”给出了错误的答案。

您的算法返回 7(即使它比字符串长!)。

正确答案是0。

(请注意，这个错误也可能出现在您找到算法描述的任何地方!如果您查看 wikipedia article 的历史记录/讨论，有很多编辑修复了错误 - 都声称修复了原始论文，并修复 bugfix 中的错误...)

如果你替换它似乎工作得更好:

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

与

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