Как отсортировать массив суффиксов?

Я смотрю на примеры массивов суффиксов и самых длинных общих префиксов, но я не понимаю критерии сортировки массива суффиксов. Я смотрю на пример в Википедии, где они используют банан $ Может кто-нибудь объяснить, как сортируется массив суффиксов? Моим первым инстинктом была сортировка по длине, но это явно не тот случай.

(Вот пример, который они использовали http://en.wikipedia.org/wiki/Suffix_array)

Эти суффиксы могут быть отсортированы:

Suffix  i
$       7
a$      6
ana$    4
anana$  2
banana$ 1
na$     5
nana$   3
Источник

3 ответа

Я также изо всех сил пытался понять, что такое суффиксный массив, тогда я нашел эту интуицию за суффиксным массивом и тем, как работает суффиксный массив с LCP.

Надеюсь, поможет! Если вам нужно дополнительное объяснение, я приведу здесь.

Источник

Учебник по массиву суффиксов можно найти по адресу http://discuss.codechef.com/questions/21385/a-tutorial-on-suffix-arrays

Этот учебник содержит такие вещи, как массив суффиксов? Как это устроено? Каков наиболее эффективный способ построения суффиксного массива? Каковы его применения?

надеюсь, вы получите то, что вы ищете..

Источник

Вот мой шаблон кода на ACM / ICPC, используя алгоритм DA

/* 
rank[0...7]: 4 6 8 1 2 3 5 7 
string:      a a b a a a a b 
------------------------------------------- 
 sa[1] = 3 : a a a a b         height[1] = 0 
 sa[2] = 4 : a a a b           height[2] = 3 
 sa[3] = 5 : a a b             height[3] = 2 
 sa[4] = 0 : a a b a a a a b   height[4] = 3 
 sa[5] = 6 : a b               height[5] = 1 
 sa[6] = 1 : a b a a a a b     height[6] = 2 
 sa[7] = 7 : b                 height[7] = 0 
 sa[8] = 2 : b a a a a b       height[8] = 1 
*/ 

const int MAXN = 200010;
int r[MAXN],sa[MAXN];
int ua[MAXN],ub[MAXN],uv[MAXN],us[MAXN];
int cmp(int *r,int a,int b,int l)
{return r[a] == r[b] && r[a+l]==r[b+l];}


void da(int *r,int *sa,int n,int m)   
{                                     
    int i,j,p,*x = ua,*y = ub,*t;
    for(i=0; i<m; i++)  us[i] = 0;
    for(i=0; i<n; i++)  us[x[i] = r[i]]++;
    for(i=1; i<m; i++)  us[i] += us[i-1];
    for(i=n-1; i>=0; i--)   sa[--us[x[i]]] = i;
    for(j=1,p=1; p<n; j<<=1,m=p)
    {
        for(p=0,i=n-j; i<n; i++)    y[p++] = i;
        for(i=0; i<n; i++)  if(sa[i]>=j) y[p++]=sa[i]-j;
        for(i=0; i<n; i++)  uv[i] = x[y[i]];
        for(i=0; i<m; i++)  us[i] = 0;
        for(i=0; i<n; i++)  us[uv[i]]++;
        for(i=1; i<m; i++)  us[i]+=us[i-1];
        for(i=n-1; i>=0; i--) sa[--us[uv[i]]] = y[i];
        for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i<n; i++)
           x[sa[i]] = cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    }
}

int rank[MAXN], height[MAXN];
void calh(int *r, int *sa, int n)
{
    int i, j, k = 0;
    for(i=1; i<=n; ++i) rank[sa[i]] = i;
    for(i=0; i<n; height[rank[i++]] = k)
        for(k?k--:0,j=sa[rank[i]-1]; r[i+k]==r[j+k];k++);
}

время выше O(nlogn)

В O(n) также есть время. Вы можете обратиться к этой статье: http://www.cs.cmu.edu/~guyb/realworld/papersS04/KaSa03.pdf

Источник
Другие вопросы по тегам