In the paper "Tight bounds on the complexity of the Apostoliko-Giancarlo algorithm" by Crochemore and Lecroq authors prove that algorithm performs not more than $1.5n$ comparison of characters in the processing stage. If I understand their proof correctly than there is no dependency on the bad character rule. Is it true?

Does the modification of Apostoliko-Giancarlo algorithm without bad character rule also perform not more than $1.5n$ character comparisons?

UPD: It seems, that Apostoliko-Giancarlo algorithm even without both rules (shift always by one) works in $O(n)$ and performs not more than $2n$ comparison of characters. But for $1.5n$ bound we definitely need the rule of a good suffix


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.