Suffix Arrays
A suffix array is a sorted array of all the suffixes of a given string. It is a powerful data structure used in string processing and pattern searching algorithms.
The suffix array can be constructed by comparing the suffixes of a string based on their lexicographic order. Once the suffix array is constructed, it can be used to efficiently solve various string-related problems such as substring search, longest common prefix, pattern matching, and more.
Here is an example implementation of building a suffix array in Java:
TEXT/X-JAVA
1import java.util.Arrays;
2
3class Suffix {
4
5 private int index;
6 private String suffix;
7
8 public Suffix(int index, String suffix) {
9 this.index = index;
10 this.suffix = suffix;
11 }
12
13 public int getIndex() {
14 return index;
15 }
16
17 public String getSuffix() {
18 return suffix;
19 }
20}
21
22public class SuffixArray {
23
24 public int[] buildSuffixArray(String text) {
25 int n = text.length();
26 Suffix[] suffixes = new Suffix[n];
27
28 for (int i = 0; i < n; i++) {
29 suffixes[i] = new Suffix(i, text.substring(i));
30 }
31
32 Arrays.sort(suffixes);
33
34 int[] suffixArray = new int[n];
35 for (int i = 0; i < n; i++) {
36 suffixArray[i] = suffixes[i].getIndex();
37 }
38
39 return suffixArray;
40 }
41
42 public static void main(String[] args) {
43 SuffixArray suffixArray = new SuffixArray();
44
45 String text = "banana";
46 int[] suffixes = suffixArray.buildSuffixArray(text);
47
48 System.out.println("Suffix Array:");
49 for (int suffix : suffixes) {
50 System.out.println(suffix);
51 }
52 }
53}xxxxxxxxxx32
}class SuffixArray { public int[] buildSuffixArray(String text) { int n = text.length(); Suffix[] suffixes = new Suffix[n]; for (int i = 0; i < n; i++) { suffixes[i] = new Suffix(i, text.substring(i)); } Arrays.sort(suffixes); int[] suffixArray = new int[n]; for (int i = 0; i < n; i++) { suffixArray[i] = suffixes[i].getIndex(); } return suffixArray; } public static void main(String[] args) { SuffixArray suffixArray = new SuffixArray(); String text = "banana"; int[] suffixes = suffixArray.buildSuffixArray(text); System.out.println("Suffix Array:"); for (int suffix : suffixes) { System.out.println(suffix);OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment