Java Program to Implement Suffix Array

»
This Java program is to Implement Suffix arrayIn computer science, a suffix array is a sorted array of all suffixes of a string. It is a simple, yet powerful data structure which is used, among others, in full text indices, data compression algorithms and within the field of bioinformatics.

Here is the source code of the Java program to implement suffix array. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4.  
  5. public class SuffixArray
  6. {
  7.     private String[] text;
  8.     private int length;
  9.     private int[] index;
  10.     private String[] suffix;
  11.  
  12.     public SuffixArray(String text)
  13.     {
  14.         this.text = new String[text.length()]; 
  15.  
  16.         for (int i = 0; i < text.length(); i++)
  17.         {
  18.             this.text[i] = text.substring(i, i+1);
  19.         } 
  20.  
  21.         this.length = text.length();
  22.         this.index = new int[length];
  23.         for (int i = 0; i < length; i++)
  24.         {
  25.             index[i] = i;
  26.         }	
  27.  
  28.         suffix = new String[length];
  29.     }
  30.  
  31.     public void createSuffixArray()
  32.     {   
  33.         for(int index = 0; index < length; index++)	
  34.         {
  35.             String text = "";
  36.             for (int text_index = index; text_index < length; text_index++)
  37.             {
  38.                 text+=this.text[text_index];
  39.             } 
  40.             suffix[index] = text;
  41.         }
  42.  
  43.         int back;
  44.         for (int iteration = 1; iteration < length; iteration++)
  45.         {
  46.             String key = suffix[iteration];
  47.             int keyindex = index[iteration];
  48.  
  49.             for (back = iteration - 1; back >= 0; back--)
  50.             {
  51.                 if (suffix[back].compareTo(key) > 0)
  52.                 {
  53.                     suffix[back + 1] = suffix[back];
  54.                     index[back + 1] = index[back];
  55.                 }
  56.                 else
  57.                 {
  58.                     break;
  59.                 }
  60.             }
  61.             suffix[ back + 1 ] = key;
  62.             index[back + 1 ] = keyindex;
  63.         }
  64.  
  65.         System.out.println("SUFFIX \t INDEX");
  66.         for (int iterate = 0; iterate < length; iterate++)
  67.         {		
  68.             System.out.println(suffix[iterate] + "\t" + index[iterate]);
  69.         }
  70.     }
  71.  
  72.  
  73.     public static void main(String...arg)throws IOException
  74.     {
  75.         String text = "";
  76.         BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  77.         System.out.println("Enter the Text String ");
  78.         text = reader.readLine();
  79.  
  80.         SuffixArray suffixarray = new SuffixArray(text);
  81.         suffixarray.createSuffixArray();
  82.     }	
  83. }

advertisement
$javac SuffixArray.java
$java SuffixArray
Enter the Text String 
banana
 
SUFFIX 	 INDEX
a         5
ana	  3
anana	  1
banana	  0
na	  4
nana	  2

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.