Тема: нестыковки в статье suffix_array
Алгоритм построения lcp на http://e-maxx.ru/algo/suffix_array не соответствует своему описанию: в описании написано что заводится массив pos а в коде вместо него используются 2 массива lpos и rpos причем с абсолютно одинаковым содержимым. Построение lcp не требует строки
lcpn[i] = min (n, lcpn[i]); т.к. построение suf_array требует дописывания $ в конец строки => при пострении lcp новой строки он не может получиться больше n
При построении lcp используется алгоритм построения suf_array, который описан ранее, но алгоритм построения suf_array подразумевает инициализацию, а при построении lcp алгоритм suf_array пропускается, но показано что он не требует инициализации(т.е. основной цикл начинается с 0), в результате чего если писать реализацию lcp на suf_array, который написан здесь, придется по другому инициализировать массив lcp (в соответсвии с посчитаными при инициализации suf_array классами эквивалантности)
Так же в описании алгоритма
Наибольший общий префикс двух подстрок: способ с дополнительной памятью
допущена ошибка - в описании написано что он позволяет отвечать на запросы за O(1) с константой log_n где log_n это
Здесь через log_n обозначена константа, равная логарифму n по основанию 2, округлённому вниз.
но n = |s| => этот алгоритм позволяет отвечать на запрос за O(log(|s|)) а не за константу
И добавьте пожалуйста в алгоритмы построения lcp алгоритм описанный здесь http://habrahabr.ru/blogs/algorithm/115346/
он проще и к тому же работает за O(n)