Тема: Суффиксный массив
второй блок кода
написано cnt[maxlen]
должно быть cnt[alphabet]
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Feedback » Суффиксный массив
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
второй блок кода
написано cnt[maxlen]
должно быть cnt[alphabet]
смотри ниже. Там cnt используется и для других целей.
реализация LCP
написано:
for (int i=0; i<n; ++i)
rpos[p[ i]] = i;
for (int i=n-1; i>=0; --i)
lpos[p[ i]] = i;
должно быть:
for (int i=0; i<n; ++i)
rpos[c[p[ i]]] = i;
for (int i=n-1; i>=0; --i)
lpos[c[p[ i]]] = i;
Да, кажется, это правильные исправления, хотя я не проверял на тестах...
В нулевой итерации ошибка.
вместо:
for (int i=0; i<n; ++i)
p[--cnt[s[i]]] = i;
должно быть:
for (int i=n-1; i>=0; --i)
p[--cnt[s[i]]] = i;
В последующих итерациях, например, соотвествующий цикл идёт по убыванию.
Убедиться в неправильности написанного можно даже на приведённой в пример строке "aaba". Для неё на нулевой итерации p должно получиться равным [0, 1, 3, 2] (или аналогичный вариант, главное, чтобы p[2] > p[0], p[1], p[3]). А получается [3, 1, 0, 2] (p[2] < p[0], p[1], p[3]). Там ещё и выход за границы массива при исполнении происходит, но это нивелируется тем, что p брали с запасом.
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Feedback » Суффиксный массив