c - 字符串中的布斯算法

Question

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

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

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

Answer 1

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

您的算法返回 7（即使这比字符串长！）。

正确答案是 0。

（请注意，此错误也可能出现在您找到算法描述的任何地方！如果您查看维基百科文章的历史/讨论，则有很多修复错误的编辑 - 都声称修复了原始论文中的错误，并且修复错误修复中的错误...）

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

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

和

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