문자열의 부스 알고리즘

Question

O (n) 시간에 Booth Algorithm을 사용하여 SPOJ에서이 problem을 풀려고했지만 시도한 모든 테스트 케이스에서 작동했지만 실패했습니다.
그런 다음 나는 O (n^2) 시간에 Brute force 방식으로 해냈다. 두 경우에 대한 코드를 첨부했는데, 어디서 잘못되었는지 말해 주시거나 Booth algo가이 문제에 대한 정확한 접근 방법입니까? 첫 번째 방법의 경우 사 전적으로 작은 문자열

의 최소 회전을 찾는 문제 밤은

, 부스 알고리즘 : 두 번째 방법의 경우 http://ideone.com/J5gl5
, 브 루트 포스 : http://ideone.com/ofTeA

Answer 1

귀하의 알고리즘은 문자열에 대한 잘못된 답을 제공합니다 "ABAED", 예를 들면.

알고리즘이 7을 반환합니다 (문자열이!보다 길어도!).

정답은 0

(당신이 편집의 많은이 고정되어있는 wikipedia article의 역사/토론 보면 역시! 당신이 알고리즘에 대한 설명을 찾을 때마다에 존재할 수있는이 버그를 참고입니다 버그 - 모두) ... 원래 논문에서 버그를 수정하고, 버그 수정 버그를 해결하기 위해 주장

바꿀 경우가 훨씬 더 작동하는 것 같다

:

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

을

로3210

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