1 Отредактировано al13n (2010-12-14 15:13:09)

Тема: lcp в суффиксном массиве

Вот более простой, чем в http://e-maxx.ru/algo/suffix_array  , способ заполнения массива lcp (lcp лексикографически соседних суффиксов). За O(n), без дополнительной памяти. Я не помню, откуда я о нем узнал :)

Пройдем по всем суффиксам в порядке уменьшения длины, находя для каждого из них lcp с лексикографически следующим суффиксом, то есть заполним массив lcp в порядке перестановки, обратной к суффиксному массиву. Утверждается, что при проходе по массиву lcp в таком порядке значение lcp никогда не уменьшается больше чем на единицу за раз. Сначала код, потом доказательство.

// sufar - суффиксный массив
// src - строка длины n, для которой построен суффиксный массив
// lcp[i] - lcp строк src[sufar[i]..n-1] и src[sufar[i+1]..n-1]
void genlcp(){
    static int invsufar[maxn];
    forn(i,n)
        invsufar[sufar[i]]=i;
    int l=0;
    forn(i,n){
        l=max(0,l-1);
        int p=invsufar[i];
        if(p+1<n)
            while(src[i+l]==src[sufar[p+1]+l])
                ++l;
        lcp[p]=l;
    }
}

Доказательство:

Пусть S[i]=str[i..n] - последовательность суффиксов строки в порядке убывания длины.
Пусть есть l=lcp[k]=lcp(S[i], S[p]) - длина общего префикса i-го и p-го суффиксов,
причем p идет в суффиксном массиве сразу после i. Нужно доказать, что t=lcp(S[i+1], S[q])>=l-1,
причем q  идет в суффиксном массиве сразу после i+1.
При l<=1 доказывать нечего: t явно не меньше нуля.
При l>1 у i-го и p-го суффиксов первый символ совпадает, кроме того S[p]>S[i].
Рассмотрим суффиксы S[i+1] и S[p+1], полученные удалением первого совпадающего символа из S[i] и S[p].
Ясно, что S[p+1]>S[i+1]. Значит t=lcp(S[i+1],S[q])>=lcp(S[i+1],S[p+1])=l-1,
т.к. q либо совпадает с p+1, либо лежит в суффиксном массиве между i+1 и p+1.

2

Re: lcp в суффиксном массиве

http://e-maxx.ru/forum/viewtopic.php?id=269

3

Re: lcp в суффиксном массиве

Да, никак руки не дойдут. А старый LCP, который у меня описан, прибить надо smile