1

Тема: Наибольший общий префикс двух подстрок

Алгоритм поиска lcp на http://e-maxx.ru/algo/suffix_array не всегда срабатывает sad

В частности if (c[a] != c[ b]) -> lcpn[ i] = lcp[pos[a]];  может быть не верно

для строки "abaabca"

на втором шаге "abca" идет перед "baabca", lcpn копируется с предыдущего и получается равным 1.

2

Re: Наибольший общий префикс двух подстрок

cpn[ i] =  rmq_get (pos[a], pos[ b] - 1);  вроде ближе к истине для c[a] != c[ b] ...

3

Re: Наибольший общий префикс двух подстрок

Хм. Этот код, по идее, где-то проходил тестирование... Что же, under investigation smile

4

Re: Наибольший общий префикс двух подстрок

Кстати такой lcp подсчет сейчас уже не модный все равно smile

На http://citeseerx.ist.psu.edu/viewdoc/do … p;type=pdf описан очень простой O(N)  алгоритм для построения lcp из уже найденного suffixArray.

Как-то так:

void calcLcp()
{
    int q = 0, j;
    for(int i = 0; i < N; i++)
    {
        if(buckets[ i ]==0)
            continue;
        j = suffixarray[buckets[ i]-1];
        while(s[i+q] == s[j+q])
            q++;
        lcp[buckets[ i ]-1] = q;
        if (q > 0) q--;
    }
    return;
}

5

Re: Наибольший общий префикс двух подстрок

Понял ошибку, сейчас делаю фикс в описании.

Проблема была в том, что когда есть несколько одинаковых блоков на каком-то уровне k, то при вычислении LCP на уровне k+1 мы берём с предыдущего уровня не тот LCP:

lcpn[i] = lcp[pos[a]];

Фикс идейно несложный: для каждого класса эквивалентности надо запоминать самую последнюю в перестановке строку из этого класса.

6

Re: Наибольший общий префикс двух подстрок

А нету какого-нибудь простого алгоритма именно для LCP в отсортированном массиве циклических сдвигов, а не суффиксов?

Re: Наибольший общий префикс двух подстрок

2rf пишет:

А нету какого-нибудь простого алгоритма именно для LCP в отсортированном массиве циклических сдвигов, а не суффиксов?

Можно хешами за O(logN) - lcp двух соседних сдвигов.

8

Re: Наибольший общий префикс двух подстрок

Так описанный выше метод и работает для сдвигов (см. пост Oleg, могу выложить и свой код). Вообще суфф. массив же на самом деле для сдвигов строится, это с помощью спец. символа его обычно заставляют работать для суффиксов.

9

Re: Наибольший общий префикс двух подстрок

Хммм, очень интересно как он работает например для строки acbacb.

10

Re: Наибольший общий префикс двух подстрок

Может кто-нибудь подскажет хорошую книжку про строки, в которой есть что-нибудь про суффиксные массивы?

11

Re: Наибольший общий префикс двух подстрок

У меня на строке aaba lcp выходят (0),1,1,0.
Это я что-то криво реализовал, или он действительно работает для суффиксов? Вроде бы i+h<n, j+h<n, раз мы проверяем s[i+h] и s[j+h].