Конструкция массива суффикса

Question

Я изучаю строение массива суффиксов из этого link.

Вот код, который я портирован из C++ в Java

class Entry implements Comparable<Entry> { 

    int [] nr = new int[2]; 
    int p=0; 

    public int compareTo(Entry that){ 
     if (this.nr[0] == that.nr[0]){ 
      if(this.nr[1] < that.nr[1]){ 
       return 1; 
      }else{ 
       return 0; 
      } 
     }else if(this.nr[0]<that.nr[0]){ 
      return 1; 
     }else{ 
      return 0; 
     } 
    } 
} 

public class SuffixArray { 

    private static final int MAXN = 65536; 
    private static final int MAXLG = 17; 

    private static Entry [] entries = new Entry[MAXN]; 
    private static int [][] matrix = new int [MAXLG] [MAXN]; 

    private static int step=0, count=0; 
    private static int N=0; 

    public static void process(String S) { 

     N = S.length(); 
     for(int i=0;i<N;i++){ 
      matrix[0][i] = (S.charAt(i)-'a'); 
     } 
     for(int i=0;i<N;i++){ 
      entries[i] = new Entry(); 
     } 

     for(step=1,count=1; (count>>1)<N;step++, count<<=1){ 
      for(int i=0;i<N;i++){ 
       entries[i].nr[0] = matrix[step-1][i];     
       entries[i].nr[1] = 
        i + ((count<N) ? matrix[step-1][i+count] : -1) ; 
       entries[i].p=i; 
      }    
      Arrays.sort(entries, 0, N, new EntryComparator()); 
      for(int i=0;i<N;i++){ 
       matrix[step][entries[i].p]=i;   
       if(i>0 
        && entries[i].nr[0]== entries[i-1].nr[0]   
        && entries[i].nr[1]==entries[i-1].nr[1]) { 
       matrix[step][entries[i].p]= matrix[step][entries[i-1].p]; 
       } 
      } 
     }   
    } 

    public static void main(String[] args) { 

     String S ="mississippi"; 
     process(S); 
    } 

Пост говорит, что вы можете получить массив суффиксов из последней строки матрицы.
Но какова последняя строка матрицы?
Для строки «Миссисипи» я всегда вижу массив в матрице [N-1] как все нули.
Я также не вижу ошибок в коде.
Может ли кто-нибудь помочь мне определить, где я ошибаюсь?
Как я могу получить массив суффикса из матрицы?

Answer 1

После много отладки я получил ответ. Склеивание код, который я разработал для поиска суффиксов массивов:

class Entry implements Comparable<Entry> { 

    int [] nr = new int[2]; 
    int p=0; 

    public int compareTo(Entry that){ 

     if(this.nr[0] == that.nr[0]) { 
      if (this.nr[1] < that.nr[1]) { 
       return -1; 
      } else { 
       return 0; 
      } 
     }else if (this.nr[0] < that.nr[0]) { 
      return -1; 
     } return 0; 
    } 

} 

public class SuffixArray { 

    private static final int MAXN = 65536; 
    private static final int MAXLG = 17; 

    private static Entry [] entries = new Entry[MAXN]; 
    private static int [][] matrix = new int [MAXLG] [MAXN]; 

    private static int step=0, count=0; 
    private static int N=0; 

    public static void process(String S) { 

     N = S.length(); 
     for(int i=0;i<N;i++){ 
      matrix[0][i] = (S.charAt(i)-'a'); 
     } 

     for(int i=0;i<MAXLG;i++){ 
      entries[i] = new Entry(); 
     } 

     for(step=1,count=1; (count>>1)<N;step++, count<<=1) { 

      for(int i=0;i<N;i++){ 
       entries[i].nr[0] = matrix[step-1][i]; 
       entries[i].nr[1] = (i+count<N) ? matrix[step-1][i+count] : -1 ;     
       entries[i].p=i; 
      } 

      Arrays.sort(entries,0,N); 

      for(int i=0;i<N;i++){ 
       matrix[step][entries[i].p]=i; 
       if(i>0 
        && entries[i].nr[0]== entries[i-1].nr[0] 
        && entries[i].nr[1]==entries[i-1].nr[1]) {      
        matrix[step][entries[i].p]= matrix[step][entries[i-1].p]; 
       } 
      } 
     } 
    } 

    public static void main(String[] args) { 
     String S ="banana"; 
     process(S); 
    } 
} 

S = "банан" и N = Len (S) = 5

Принимая из индекса 0, в последней строке в матрице при N = 4.

матрица [4] [0 .... 5] это массив суффиксов

суффикс массива [3,2,5,1,4,0]