fork download
copy 
  1. import java.util.*;
  2.  
  3. class Discuss {
  4.  
  5.   // suffix array in O(n*log^2(n))
  6.   public static Integer[] suffixArray(CharSequence s)  {
  7.     int n = s.length();
  8.     Integer[] sa = new Integer[n];
  9.     int[] rank = new int[n];
  10.     for (int i = 0; i < n; i++) {
  11.       sa[i] = i;
  12.       rank[i] = s.charAt(i);
  13.     }
  14.     for (int len = 1; len < n; len *= 2) {
  15.       long[] rank2 = new long[n];
  16.       for (int i = 0; i < n; i++)
  17.         rank2[i] = ((long) rank[i] << 32) + (i + len < n ? rank[i + len] + 1 : 0);
  18.  
  19.       //Arrays.sort(sa, (a, b) -> Long.compare(rank2[a], rank2[b]));
  20.  
  21.       class MyComparator implements Comparator<Integer> {
  22.     	      private final long[] array;
  23.     	      public MyComparator(long[] array)
  24.     	      {
  25.     	          this.array = array;
  26.     	      }
  27.  
  28.     	      @Override
  29.     	      public int compare(Integer index1, Integer index2)
  30.     	      {
  31.     	          return Long.compare(array[index1],array[index2]);
  32.     	      }
  33.     	  }
  34.  
  35.       MyComparator comp = new MyComparator(rank2);
  36.       Arrays.sort(sa, comp);
  37.  
  38.  
  39.       for (int i = 0; i < n; i++)
  40.         rank[sa[i]] = i > 0 && rank2[sa[i - 1]] == rank2[sa[i]] ? rank[sa[i - 1]] : i;
  41.     }
  42.     return sa;
  43.   }
  44.  
  45.  
  46.   // random test
  47.   public static void main(String[] args) {
  48.     Random rnd = new Random(1);
  49.     for (int step = 0; step < 100000; step++) {	
  50.       int n = rnd.nextInt(100);
  51.       StringBuilder s = new StringBuilder();
  52.       for (int i = 0; i < n; i++)
  53.         s.append((char) ('\0' + rnd.nextInt(10)));
  54.       Integer[] sa = suffixArray(s);
  55.       for (int i = 0; i + 1 < n; i++)
  56.         if (s.substring(sa[i]).compareTo(s.substring(sa[i + 1])) >= 0)
  57.           throw new RuntimeException();
  58.     }
  59.     System.out.println("Test passed");
  60.   }
  61. }
Success #stdin #stdout 3.98s 381568KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Test passed
https://ideone.com/jp5rw7
language:
Java (12.0.1)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!