fork(1) download
copy 
  1.  
  2. import java.util.ArrayList;
  3. import java.util.HashMap;
  4.  
  5.  
  6.  
  7.  
  8. class StringSuffixArray {
  9.  
  10.  
  11. 	public static void main(String[] args) {
  12. 		String input = "banana";
  13. 		NodeMap nodeMapObj = new NodeMap();
  14. 		for(int i=0;i<input.length();i++){
  15. 			nodeMapObj.add(i,input.substring(i));
  16. 		}
  17. 		nodeMapObj.print();
  18. 		System.out.println("done");
  19.  
  20. 	}
  21.  
  22.  
  23. }
  24. class Result{
  25. 	int index;
  26. 	String val;
  27. 	public Result(int index,String val) {
  28. 		this.index=index;
  29. 		this.val=val;
  30. 	}
  31. 	@Override
  32. 	public String toString() {
  33. 		// TODO Auto-generated method stub
  34. 		return  index +" " + val;
  35. 	}
  36. }
  37.  
  38. class Node{
  39. 	int index;
  40. 	Character charValue=null;
  41. 	String stringValue;
  42. 	NodeMap map;
  43. 	public ArrayList<Result> getStrings(){
  44. 		ArrayList<Result> mapList = new ArrayList<Result>();
  45. 		// Print node alphabetically
  46. 		if(map==null){
  47. 			if(stringValue!=null){
  48. 				Result r1= new Result(this.index,charValue + stringValue);
  49. 				mapList.add(r1);
  50. 			}else{
  51. 				Result r1= new Result(this.index, charValue+"");
  52. 				mapList.add(r1);
  53. 			}
  54. 		}else{
  55. 			// Map is not null. So print all all the map contents
  56. 	        if(map.get(null)!=null && map.get(null).charValue==null){
  57. 	        	Result r1= new Result(map.get(null).index,charValue+"");
  58. 	        	mapList.add(r1);
  59. 	        }			
  60. 	        for( char ch = 'a' ; ch <= 'z' ; ch++ ){
  61. 		           Node node = map.get(ch);
  62. 		           if(node !=null){
  63. 		        	   ArrayList<Result>  internalList = node.getStrings();	         
  64. 		        	   for(Result str:internalList){
  65. 		        		   Result r1= new Result(str.index,charValue+str.val);
  66. 		        		   mapList.add(r1);
  67. 		        	   }
  68. 		           }
  69. 	        }
  70. 		}
  71.         return mapList;
  72. 	}
  73.  
  74. 	}
  75.  
  76. class NodeMap{
  77. 	HashMap<Character,Node> map;
  78.  
  79. 	public void add(int index,String inputString){
  80. 	 if(inputString != null){
  81. 		if(map==null){
  82. 			// First time call. Create Map and add String
  83. 			map = new HashMap<Character,Node>();
  84. 		}
  85. 		// Map already present check if character already there
  86. 		Node charNode = map.get(inputString.charAt(0));
  87. 		if(charNode==null){
  88. 			// Character not present in map. Add map entry
  89. 			Node node = new Node();
  90. 			node.charValue=inputString.charAt(0);
  91. 			node.index = index;
  92. 			if(inputString.length()>1){
  93. 				 node.stringValue=inputString.substring(1);
  94. 			}else{
  95. 				node.stringValue=null;
  96. 			}
  97. 			node.map=null;
  98. 			map.put(inputString.charAt(0), node);			
  99. 		}else{ // Character present 
  100. 			// Check if map of node is already populated. if yes, just add input string in that map 
  101. 			// If map is not present; then create map. Add existing value in map. and then add new string in map 
  102. 			// This is node of first character of input string. So sub-map should be for second character
  103. 			if(charNode.map==null){
  104. 				// Node does not have map.  So create sub-map.
  105. 				charNode.map = new NodeMap();
  106. 				charNode.map.add(charNode.index,charNode.stringValue);
  107. 			}
  108. 			if(inputString.length()>1){
  109. 				charNode.map.add(index,inputString.substring(1));
  110. 			}else{
  111. 				charNode.map.add(index,null);
  112. 			}
  113.  
  114. 			charNode.stringValue=null;
  115. 		}
  116. 	}else{
  117. 		// Add a null node. Indicating end of string
  118. 		Node n = new Node();
  119. 		n.index=index;
  120. 		n.charValue=null;
  121. 		map.put(null,n);
  122. 	}
  123. }
  124. 	public Node get(Character ch){
  125. 		return map.get(ch);
  126. 	}
  127.  
  128. 	public void print(){
  129. 		// Map is not null. So print all all the map contents
  130. 		ArrayList<Result> finalArray= new ArrayList<Result>();
  131.         for( char ch = 'a' ; ch <= 'z' ; ch++ ){
  132.         	Node node = map.get(ch);
  133.         	if(node!=null){
  134.         		finalArray.addAll(node.getStrings());
  135.         	}
  136. 	    }
  137.  
  138.         for(Result rs : finalArray){
  139.         	System.out.println(rs);
  140.         }
  141. 	}
  142. }
  143.  
  144.  
  145.  
  146.  
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
5 a
3 ana
1 anana
0 banana
4 na
2 nana
done
https://ideone.com/TBhfxI
language:
Java (HotSpot 12)
created:
10 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!