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

Question

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

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

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

Suffix i 
$  7 
a$  6 
ana$ 4 
anana$ 2 
banana$ 1 
na$  5 
nana$ 3 

Answer 1

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

/* 
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

Answer 2

Я также попытался понять массив суффикса, тогда я нашел это intuition behind suffix array and how suffix array with LCP works.

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

Answer 3

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

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

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