Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.

I keep getting compiler errors with an implementation of a suffix array by Arrays.sort.

I get the following errors:

a cannot be resolved to a variable
Syntax error on token ",", . expected
Syntax error on token "-", -- expected
a cannot be resolved to a variable
b cannot be resolved to a variable

In the following code:

import java.util.*;

public class SuffixArray {

  // sort suffixes of S in O(n*log(n))
  public static int[] suffixArray(CharSequence S) {
    int n = S.length();
    Integer[] order = new Integer[n];
    for (int i = 0; i < n; i++)
      order[i] = n - 1 - i;

    // stable sort of characters
    Arrays.sort(order, (a, b) -> Character.compare(S.charAt(a), S.charAt(b)));

    int[] sa = new int[n];
    int[] classes = new int[n];
    for (int i = 0; i < n; i++) {
      sa[i] = order[i];
      classes[i] = S.charAt(i);
    }
    // sa[i] - suffix on i'th position after sorting by first len characters
    // classes[i] - equivalence class of the i'th suffix after sorting by first len characters

    for (int len = 1; len < n; len *= 2) {
      int[] c = classes.clone();
      for (int i = 0; i < n; i++) {
        // condition sa[i - 1] + len < n simulates 0-symbol at the end of the string
        // a separate class is created for each suffix followed by simulated 0-symbol
        classes[sa[i]] = i > 0 && c[sa[i - 1]] == c[sa[i]] && sa[i - 1] + len < n && c[sa[i - 1] + len / 2] == c[sa[i] + len / 2] ? classes[sa[i - 1]] : i;
      }
      // Suffixes are already sorted by first len characters
      // Now sort suffixes by first len * 2 characters
      int[] cnt = new int[n];
      for (int i = 0; i < n; i++)
        cnt[i] = i;
      int[] s = sa.clone();
      for (int i = 0; i < n; i++) {
        // s[i] - order of suffixes sorted by first len characters
        // (s[i] - len) - order of suffixes sorted only by second len characters
        int s1 = s[i] - len;
        // sort only suffixes of length > len, others are already sorted
        if (s1 >= 0)
          sa[cnt[classes[s1]]++] = s1;
      }
    }
    return sa;
  }

  // sort rotations of S in O(n*log(n))
  public static int[] rotationArray(CharSequence S) {
    int n = S.length();
    Integer[] order = new Integer[n];
    for (int i = 0; i < n; i++)
      order[i] = i;
    Arrays.sort(order, (a, b) -> Character.compare(S.charAt(a), S.charAt(b)));
    int[] sa = new int[n];
    int[] classes = new int[n];
    for (int i = 0; i < n; i++) {
      sa[i] = order[i];
      classes[i] = S.charAt(i);
    }
    for (int len = 1; len < n; len *= 2) {
      int[] c = classes.clone();
      for (int i = 0; i < n; i++)
        classes[sa[i]] = i > 0 && c[sa[i - 1]] == c[sa[i]] && c[(sa[i - 1] + len / 2) % n] == c[(sa[i] + len / 2) % n] ? classes[sa[i - 1]] : i;
      int[] cnt = new int[n];
      for (int i = 0; i < n; i++)
        cnt[i] = i;
      int[] s = sa.clone();
      for (int i = 0; i < n; i++) {
        int s1 = (s[i] - len + n) % n;
        sa[cnt[classes[s1]]++] = s1;
      }
    }
    return sa;
  }

  // longest common prefixes array in O(n)
  public static int[] lcp(int[] sa, CharSequence s) {
    int n = sa.length;
    int[] rank = new int[n];
    for (int i = 0; i < n; i++)
      rank[sa[i]] = i;
    int[] lcp = new int[n - 1];
    for (int i = 0, h = 0; i < n; i++) {
      if (rank[i] < n - 1) {
        for (int j = sa[rank[i] + 1]; Math.max(i, j) + h < s.length() && s.charAt(i + h) == s.charAt(j + h); ++h)
      ;
        lcp[rank[i]] = h;
        if (h > 0)
          --h;
      }    
    }
    return lcp;
  }

  // Usage example
  public static void main(String[] args) {
    String s1 = "abcab";
    int[] sa1 = suffixArray(s1);

    // print suffixes in lexicographic order
    for (int p : sa1)
      System.out.println(s1.substring(p));

    System.out.println("lcp = " + Arrays.toString(lcp(sa1, s1)));

    // random test
    Random rnd = new Random(1);
    for (int step = 0; step < 100000; step++) {
      int n = rnd.nextInt(100) + 1;
      StringBuilder s = new StringBuilder();
      for (int i = 0; i < n; i++)
        s.append((char) ('\1' + rnd.nextInt(10)));
      int[] sa = suffixArray(s);
      int[] ra = rotationArray(s.toString() + '\0');
      int[] lcp = lcp(sa, s);
  for (int i = 0; i + 1 < n; i++) {
        String a = s.substring(sa[i]);
        String b = s.substring(sa[i + 1]);
        if (a.compareTo(b) >= 0
            || !a.substring(0, lcp[i]).equals(b.substring(0, lcp[i]))
            || (a + " ").charAt(lcp[i]) == (b + " ").charAt(lcp[i])
            || sa[i] != ra[i + 1])
          throw new RuntimeException();
      }
    }
    System.out.println("Test passed");
  }
}
share|improve this question
1  
Which compilation errors? –  Eran Oct 12 at 6:26
    
And why did you say the same sentences three times? –  Seelenvirtuose Oct 12 at 6:28
1  
Are you compiling this code with Java 8? This code contains lambda expressions. –  Eran Oct 12 at 6:29
    
@Seelenvirtuose If you're talking about the errors themselves, it looks like from the raw markdown that the OP pasted the error output and just didn't tidy up the formatting all the way. –  Dennis Meng Oct 12 at 7:18
    
@DennisMeng No, I talked about the text in the very first version of this "question". He copy-pasted this little text three times. –  Seelenvirtuose Oct 12 at 7:22

1 Answer 1

up vote 0 down vote accepted

a cannot be resolved to a variable
Syntax error on token ",", . expected
Syntax error on token "-", -- expected
a cannot be resolved to a variable
b cannot be resolved to a variable

You are getting these errors on this line (which appears twice in the code) :

Arrays.sort(order, (a, b) -> Character.compare(S.charAt(a), S.charAt(b)));
                    ^^    ^                             ^            ^

The reason must be that you are not compiling the code in Java 8. Lambda expressions require Java 8.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.