массива суффиксов с помощью Manber Майерс алгоритм

Question

Я пытался идти через теорию в статье http://webglimpse.net/pubs/suffix.pdf

Но я бы потерял, когда они говорят

Пусть Ai будет первой суф фи х в первом ведре (т.е. Pos [0] = i), и рассмотрим Ai-h (если ih < 0, то мы игнорируем Ai и берем suf fi of Pos [1] и т. д.). Так как Ai начинается с наименьшей строки символа h, Ai-h должен быть первым в своем 2-х ведро.

Я не могу понять это утверждение. Почему Ai-h можно игнорировать, если i-h < 0. Как определяется положение в const-времени, когда i-h> 0 в фазе 1?

Один образец осущ является http://belbesy.wordpress.com/2012/10/10/spoj-649-distinct-substrings-suffix-arrays-nlgn/

Answer 1

Я настоятельно рекомендую, вместо того, чтобы пытаться понять код C++, пройти через этот Python implementation of the Manbers-Myers suffix array construction algorithm, вручную, для простого примера 5 символов.

Поскольку версия Python составляет всего около 15 строк кода, так что это довольно легко.

Даже если вы не понимаете Python, рассматривайте его как псевдокод, а Google - синтаксис, который вы не понимаете.

Лично я прошел через одну строку из 5 символов вручную, и этого было достаточно, чтобы помочь мне понять, как работает алгоритм.