Как вычислить массив LCP для массива суффиксов? Он не должен быть самым эффективным. O(n log n) или O(n) подойдет. Что-то относительно легко закодировать, если это возможно.
Массив LCP для массива суффиксов
Ответы (1)
Вот простая реализация C++. Самый длинный общий префикс (LCP) будет сохранен в массиве lcp[MAX] :)
char str[MAX];
int n,gap,sa[MAX],pos[MAX],tmp[MAX],lcp[MAX];
// sa stores the sorted index of the suffixes
// pos stores the serial number of a index in the sorted sequence
bool sufCmp(int i, int j)
{
if(pos[i]!=pos[j])
return pos[i]<pos[j];
i+=gap;
j+=gap;
return (i<n&&j<n)?pos[i]<pos[j]:i>j;
}
void buildSA()
{
n=strlen(str);
for(int i=0;i<n;i++)
sa[i]=i,pos[i]=str[i];
for(gap=1;;gap*=2)
{
sort(sa,sa+n,sufCmp);
for(int i=0;i<n-1;i++)
tmp[i+1]=tmp[i]+sufCmp(sa[i],sa[i+1]);
for(int i=0;i<n;i++)
pos[sa[i]]=tmp[i];
if(tmp[n-1]==n-1)
break;
}
}
void buildLCP()
{
for(int i=0,k=0;i<n;++i)
{
if(pos[i]==n-1)
lcp[pos[i]]=0;
else
{
for(int j=sa[pos[i]+1];str[i+k]==str[j+k];)
k++;
lcp[pos[i]]=k;
if(k)
k--;
}
}
}
person
Ali Akber
schedule
11.12.2014