fork(7) download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. class TestClass {
  5. 	public static long MOD = 1000000007;
  6.  
  7. 	public static void main(String[] args) throws FileNotFoundException {
  8. 		// PrintWriter out = new PrintWriter(new FileOutputStream(new File(
  9. 		// "output.txt")));
  10. 		PrintWriter out = new PrintWriter(System.out);
  11. 		Scanner in = new Scanner();
  12. 		int t = in.nextInt();
  13. 		long[][] C = new long[5001][5001];
  14. 		for (int z = 0; z < t; z++) {
  15. 			int n = in.nextInt();
  16. 			int q = in.nextInt();
  17. 			String s = in.next();
  18. 			int[][] cur = new int[n][];
  19. 			int[][] count = new int[n][n];
  20. 			int[] length = new int[n];
  21. 			for (int i = 0; i < n; i++) {
  22. 				cur[i] = Z(s.substring(i).toCharArray());
  23. 				for (int j = 1; j < cur[i].length; j++) {
  24. 					if (cur[i][j] > length[j + i]) {
  25. 						for (int k = i + length[j + i]; k < i + cur[i][j]; k++) {
  26. 							count[i][k]++;
  27. 						}
  28. 						length[j + i] = cur[i][j];
  29. 					}
  30.  
  31. 				}
  32. 			}
  33. 			int[] F = new int[n + 1];
  34. 			for(int i = 0; i < n; i++){
  35. 				for(int j = i; j < n; j++){
  36. 					int v = count[i][j] + (length[i] < (j - i + 1) ? 1 : 0);
  37. 					F[v]++;
  38. 				}
  39. 			}
  40. 			for (int i = 0; i <= n; i++){
  41. 				for (int j = 0; j <= Math.min(i, n); j++) {
  42. 					if (j == 0 || j == i) {
  43. 						C[i][j] = 1;
  44. 						continue;
  45.  
  46. 					}
  47.  
  48. 					C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
  49. 					C[i][j] %= MOD;
  50. 				}
  51. 			}
  52. 			long[] ans = new long[n + 1];
  53.  
  54. 			for (int i = 1; i <= n; i++) {
  55. 				for (int j = i; j <= n; j++) {
  56. 					ans[i] += F[j] * C[j][i];
  57. 					ans[i] %= MOD;
  58. 				}
  59. 			}
  60. 			for(int i = 0; i < q; i++){
  61. 				int v = in.nextInt();
  62. 				if(v <= n){
  63. 					out.println(ans[v]);
  64. 				}else{
  65. 					out.println(0);
  66. 				}
  67. 			}
  68. 		}
  69.  
  70. 		out.close();
  71. 	}
  72.  
  73. 	public static int[] Z(char[] s) {
  74. 		int[] z = new int[s.length];
  75. 		int n = s.length;
  76. 		int L = 0, R = 0;
  77. 		for (int i = 1; i < n; i++) {
  78. 			if (i > R) {
  79. 				L = R = i;
  80. 				while (R < n && s[R - L] == s[R])
  81. 					R++;
  82.  
  83. 				z[i] = R - L;
  84.  
  85. 				R--;
  86. 			} else {
  87. 				int k = i - L;
  88. 				if (z[k] < R - i + 1) {
  89. 					z[i] = z[k];
  90. 				} else {
  91. 					L = i;
  92. 					while (R < n && s[R - L] == s[R])
  93. 						R++;
  94. 					z[i] = R - L;
  95. 					R--;
  96. 				}
  97. 			}
  98. 		}
  99. 		return z;
  100. 	}
  101.  
  102. 	public static int[] KMP(String val) {
  103. 		int i = 0;
  104. 		int j = -1;
  105. 		int[] result = new int[val.length() + 1];
  106. 		result[0] = -1;
  107. 		while (i < val.length()) {
  108. 			while (j >= 0 && val.charAt(j) != val.charAt(i)) {
  109. 				j = result[j];
  110. 			}
  111. 			j++;
  112. 			i++;
  113. 			result[i] = j;
  114. 		}
  115. 		return result;
  116.  
  117. 	}
  118.  
  119. 	public static boolean nextPer(int[] data) {
  120. 		int i = data.length - 1;
  121. 		while (i > 0 && data[i] < data[i - 1]) {
  122. 			i--;
  123. 		}
  124. 		if (i == 0) {
  125. 			return false;
  126. 		}
  127. 		int j = data.length - 1;
  128. 		while (data[j] < data[i - 1]) {
  129. 			j--;
  130. 		}
  131. 		int temp = data[i - 1];
  132. 		data[i - 1] = data[j];
  133. 		data[j] = temp;
  134. 		Arrays.sort(data, i, data.length);
  135. 		return true;
  136. 	}
  137.  
  138. 	public static int digit(long n) {
  139. 		int result = 0;
  140. 		while (n > 0) {
  141. 			n /= 10;
  142. 			result++;
  143. 		}
  144. 		return result;
  145. 	}
  146.  
  147. 	public static double dist(long a, long b, long x, long y) {
  148. 		double val = (b - a) * (b - a) + (x - y) * (x - y);
  149. 		val = Math.sqrt(val);
  150. 		double other = x * x + a * a;
  151. 		other = Math.sqrt(other);
  152. 		return val + other;
  153.  
  154. 	}
  155.  
  156. 	public static class Point implements Comparable<Point> {
  157.  
  158. 		int x, y;
  159.  
  160. 		public Point(int start, int end) {
  161. 			this.x = start;
  162. 			this.y = end;
  163. 		}
  164.  
  165. 		@Override
  166. 		public int hashCode() {
  167. 			int hash = 5;
  168. 			hash = 47 * hash + this.x;
  169. 			hash = 47 * hash + this.y;
  170. 			return hash;
  171. 		}
  172.  
  173. 		@Override
  174. 		public boolean equals(Object obj) {
  175. 			if (obj == null) {
  176. 				return false;
  177. 			}
  178. 			if (getClass() != obj.getClass()) {
  179. 				return false;
  180. 			}
  181. 			final Point other = (Point) obj;
  182. 			if (this.x != other.x) {
  183. 				return false;
  184. 			}
  185. 			if (this.y != other.y) {
  186. 				return false;
  187. 			}
  188. 			return true;
  189. 		}
  190.  
  191. 		@Override
  192. 		public int compareTo(Point o) {
  193. 			return x - o.x;
  194. 		}
  195. 	}
  196.  
  197. 	public static class FT {
  198.  
  199. 		long[] data;
  200.  
  201. 		FT(int n) {
  202. 			data = new long[n];
  203. 		}
  204.  
  205. 		public void update(int index, long value) {
  206. 			while (index < data.length) {
  207. 				data[index] += value;
  208. 				index += (index & (-index));
  209. 			}
  210. 		}
  211.  
  212. 		public long get(int index) {
  213. 			long result = 0;
  214. 			while (index > 0) {
  215. 				result += data[index];
  216. 				index -= (index & (-index));
  217. 			}
  218. 			return result;
  219.  
  220. 		}
  221. 	}
  222.  
  223. 	public static long gcd(long a, long b) {
  224. 		if (b == 0) {
  225. 			return a;
  226. 		}
  227. 		return gcd(b, a % b);
  228. 	}
  229.  
  230. 	public static long pow(long a, long b) {
  231. 		if (b == 0) {
  232. 			return 1;
  233. 		}
  234. 		if (b == 1) {
  235. 			return a;
  236. 		}
  237. 		long val = pow(a, b / 2);
  238. 		if (b % 2 == 0) {
  239. 			return val * val % MOD;
  240. 		} else {
  241. 			return val * (val * a % MOD) % MOD;
  242.  
  243. 		}
  244. 	}
  245.  
  246. 	static class Scanner {
  247.  
  248. 		BufferedReader br;
  249. 		StringTokenizer st;
  250.  
  251. 		public Scanner() throws FileNotFoundException {
  252. 			// System.setOut(new PrintStream(new
  253. 			// BufferedOutputStream(System.out), true));
  254. 			br = new BufferedReader(new InputStreamReader(System.in));
  255. 			// br = new BufferedReader(new InputStreamReader(new
  256. 			// FileInputStream(new File("input.txt"))));
  257. 		}
  258.  
  259. 		public String next() {
  260.  
  261. 			while (st == null || !st.hasMoreTokens()) {
  262. 				try {
  263. 					st = new StringTokenizer(br.readLine());
  264. 				} catch (Exception e) {
  265. 					throw new RuntimeException();
  266. 				}
  267. 			}
  268. 			return st.nextToken();
  269. 		}
  270.  
  271. 		public long nextLong() {
  272. 			return Long.parseLong(next());
  273. 		}
  274.  
  275. 		public int nextInt() {
  276. 			return Integer.parseInt(next());
  277. 		}
  278.  
  279. 		public double nextDouble() {
  280. 			return Double.parseDouble(next());
  281. 		}
  282.  
  283. 		public String nextLine() {
  284. 			st = null;
  285. 			try {
  286. 				return br.readLine();
  287. 			} catch (Exception e) {
  288. 				throw new RuntimeException();
  289. 			}
  290. 		}
  291.  
  292. 		public boolean endLine() {
  293. 			try {
  294. 				String next = br.readLine();
  295. 				while (next != null && next.trim().isEmpty()) {
  296. 					next = br.readLine();
  297. 				}
  298. 				if (next == null) {
  299. 					return true;
  300. 				}
  301. 				st = new StringTokenizer(next);
  302. 				return st.hasMoreTokens();
  303. 			} catch (Exception e) {
  304. 				throw new RuntimeException();
  305. 			}
  306. 		}
  307. 	}
  308. }
Runtime error #stdin #stdout #stderr 0.06s 380160KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.lang.RuntimeException
	at TestClass$Scanner.next(Main.java:265)
	at TestClass$Scanner.nextInt(Main.java:276)
	at TestClass.main(Main.java:12)
https://ideone.com/5GYWeS
language:
Java (12.0.1)
created:
9 years ago
visibility:
secret

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!