fork download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.Arrays;
  5.  
  6.  
  7. public class Main {
  8.  
  9. 	 public static void main(String[] args) throws IOException {
  10. 		 BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
  11. 		 int t = Integer.parseInt(bf.readLine());
  12. 		 while(t-->0){
  13. 			 String s = bf.readLine();
  14. 			 int n = s.length();
  15. 			 suffixsarray x = new suffixsarray(s);
  16. 			 int res = n - x.index(0);
  17. 			 for(int i=1; i<n; i++)
  18. 				 res += (n-x.index(i)) - x.lcp(i);
  19. 			 System.out.println(res);
  20. 		 }
  21. 	}
  22. }
  23.  
  24. class suffixsarray {
  25. 	private Suffix[] suffixes;
  26.  
  27. 	public suffixsarray(String text) {
  28. 		int N = text.length();
  29. 		this.suffixes = new Suffix[N];
  30. 		for (int i = 0; i < N; i++)
  31. 			suffixes[i] = new Suffix(text, i);
  32. 		Arrays.sort(suffixes);
  33. 	}
  34.  
  35. 	private static class Suffix implements Comparable<Suffix> {
  36. 		private final String text;
  37. 		private final int index;
  38.  
  39. 		private Suffix(String text, int index) {
  40. 			this.text = text;
  41. 			this.index = index;
  42. 		}
  43.  
  44. 		private int length() {
  45. 			return text.length() - index;
  46. 		}
  47.  
  48. 		private char charAt(int i) {
  49. 			return text.charAt(index + i);
  50. 		}
  51.  
  52. 		public int compareTo(Suffix that) {
  53. 			if (this == that)
  54. 				return 0; // optimization
  55. 			int N = Math.min(this.length(), that.length());
  56. 			for (int i = 0; i < N; i++) {
  57. 				if (this.charAt(i) < that.charAt(i))
  58. 					return -1;
  59. 				if (this.charAt(i) > that.charAt(i))
  60. 					return +1;
  61. 			}
  62. 			return this.length() - that.length();
  63. 		}
  64.  
  65. 		public String toString() {
  66. 			return text.substring(index);
  67. 		}
  68. 	}
  69.  
  70. 	// length of string
  71. 	public int length() {
  72. 		return suffixes.length;
  73. 	}
  74.  
  75. 	// index of ith sorted suffix
  76. 	public int index(int i) {
  77. 		return suffixes[i].index;
  78. 	}
  79.  
  80. 	// longest common prefix of suffixes(i) and suffixes(i-1)
  81. 	public int lcp(int i) {
  82. 		return lcp(suffixes[i], suffixes[i - 1]);
  83. 	}
  84.  
  85. 	// longest common prefix of s and t
  86. 	private static int lcp(Suffix s, Suffix t) {
  87. 		int N = Math.min(s.length(), t.length());
  88. 		for (int i = 0; i < N; i++) {
  89. 			if (s.charAt(i) != t.charAt(i))
  90. 				return i;
  91. 		}
  92. 		return N;
  93. 	}
  94.  
  95. 	public String select(int i) {
  96. 		return suffixes[i].toString();
  97. 	}
  98.  
  99. 	// number of suffixes strictly less than query
  100. 	public int rank(String query) {
  101. 		int lo = 0, hi = suffixes.length - 1;
  102. 		while (lo <= hi) {
  103. 			int mid = lo + (hi - lo) / 2;
  104. 			int cmp = compare(query, suffixes[mid]);
  105. 			if (cmp < 0)
  106. 				hi = mid - 1;
  107. 			else if (cmp > 0)
  108. 				lo = mid + 1;
  109. 			else
  110. 				return mid;
  111. 		}
  112. 		return lo;
  113. 	}
  114.  
  115. 	// compare query string to suffix
  116. 	private static int compare(String query, Suffix suffix) {
  117. 		int N = Math.min(query.length(), suffix.length());
  118. 		for (int i = 0; i < N; i++) {
  119. 			if (query.charAt(i) < suffix.charAt(i))
  120. 				return -1;
  121. 			if (query.charAt(i) > suffix.charAt(i))
  122. 				return +1;
  123. 		}
  124. 		return query.length() - suffix.length();
  125. 	}
  126. }
Runtime error #stdin #stdout #stderr 0.07s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.lang.NumberFormatException: null
	at java.lang.Integer.parseInt(Integer.java:454)
	at java.lang.Integer.parseInt(Integer.java:527)
	at Main.main(Main.java:11)
https://ideone.com/0BbVs3
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!