我尝试在 O(n) 时间内使用Booth 算法在 SPOJ 中解决这个问题，但它失败了，尽管它适用于我尝试过的所有测试用例。
然后我在 O(n^2) 时间内以蛮力方式做了，它奏效了。我已经附上了这两种情况的代码，告诉我哪里出错了，或者 Booth 算法是解决这个问题的正确方法吗？
不是问题，找到字典最小字符串的最小旋转
对于第一种方法，布斯算法： http: //ideone.com/J5gl5
对于第二种方法，蛮力：http: //ideone.com/ofTeA
问问题
2218 次
1 回答
6
例如，您的算法对字符串“ABAED”给出了错误的答案。
您的算法返回 7（即使这比字符串长！）。
正确答案是 0。
（请注意，此错误也可能出现在您找到算法描述的任何地方！如果您查看维基百科文章的历史/讨论，则有很多修复错误的编辑 - 都声称修复了原始论文中的错误，并且修复错误修复中的错误...）
如果你更换它似乎工作得更好：
if( lst[i] < lst[ans+i+1] )
和
if( lst[j] < lst[ans+i+1] )
于 2012-07-26T19:23:46.350 回答