fork download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.io.PrintWriter;
  5. import java.util.HashMap;
  6. import java.util.Map;
  7.  
  8. class Ideone {
  9.  
  10. 	static final int maxn = 40000;
  11. 	static int len[] = new int[maxn], link[] = new int[maxn], count[][] = new int[2][maxn];
  12. 	static boolean vis[] = new boolean[maxn];
  13. 	static HashMap<Character, Integer> to[] = new HashMap[maxn];
  14. 	static int size = 0, last, res;
  15.  
  16. 	public static void init() {
  17. 		for (int i = 0; i < size; i++) {
  18. 			to[i].clear();
  19. 			len[i] = link[i] = count[0][i] = count[1][i] = 0;
  20. 			vis[i] = false; 
  21. 		}
  22. 		link[0] = -1;
  23. 		size = 1;
  24. 		last = res = 0;
  25. 	}
  26.  
  27. 	public static void addCharacter(Character c) {
  28. 		int p = last;
  29. 		last = size++;
  30. 		len[last] = len[p] + 1;
  31. 		for (; p != -1 && !to[p].containsKey(c); p = link[p])
  32. 			to[p].put(c, last);
  33. 		if (p == -1)
  34. 			return;
  35. 		int q = to[p].get(c);
  36. 		if (len[q] == len[p] + 1) {
  37. 			link[last] = q;
  38. 			return;
  39. 		}
  40. 		int cl = size++;
  41. 		to[cl].putAll(to[q]);
  42. 		link[cl] = link[q];
  43. 		len[cl] = len[p] + 1;
  44. 		link[last] = link[q] = cl;
  45. 		for (; p != -1 && to[p].containsKey(c) && to[p].get(c) == q; p = link[p])
  46. 			to[p].put(c, cl);
  47. 	}
  48.  
  49. 	public static int dfs(int x, int k) {
  50. 		if (vis[x])
  51. 			return res;
  52. 		vis[x] = true;
  53. 		count[0][x] = count[1][x] = 0;
  54. 		for (Map.Entry<Character, Integer> it : to[x].entrySet())
  55. 			if (it.getKey() == '#')
  56. 				count[0][x]++;
  57. 			else
  58. 				if (it.getKey() == '$')
  59. 					count[1][x]++;
  60. 				else {
  61. 					dfs(it.getValue(), k);
  62. 					count[0][x] += count[0][it.getValue()];
  63. 					count[1][x] += count[1][it.getValue()];
  64. 				}
  65. 		if (x != 0) {
  66. 			int x1 = count[0][x] != 0 ? 1 : 0;
  67. 			int x2 = count[1][x] == k ? 1 : 0;
  68. 			res += (x1 * x2 * (len[x] - len[link[x]]));
  69. 		}
  70. 		return res;
  71. 	}
  72.  
  73. 	public static void main(String[] args) throws NumberFormatException, IOException {
  74. 		for (int i = 0; i < maxn; i++)
  75. 			to[i] = new HashMap<Character, Integer>();
  76.  
  77. 		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
  78. 		PrintWriter out = new PrintWriter(System.out);
  79.  
  80. 		int t = Integer.parseInt(bf.readLine());
  81.  
  82. 		for (int tc = 1; tc <= t; tc++) {
  83. 			out.println("Case #" + tc + ":");
  84. 			String s1 = bf.readLine();
  85. 			String s2 = bf.readLine();
  86. 			int k = Integer.parseInt(bf.readLine());
  87. 			int n = s1.length(); int m = s2.length();
  88. 			init();
  89. 			for (int i = 0; i < n; i++)
  90. 				addCharacter(s1.charAt(i));
  91. 			addCharacter('#');
  92. 			for (int i = 0; i < m; i++)
  93. 				addCharacter(s2.charAt(i));
  94. 			addCharacter('$');
  95.  
  96. 			out.println(dfs(0, k));
  97. 		}
  98. 		out.flush();
  99. 		//out.close();
  100.  
  101. 	}
  102. }
Success #stdin #stdout 0.1s 380416KB
comments (?)
stdin
copy 
3
egyptnational
ecpc
1
egyptnational
ecpc
2
fastlast
bestmost
2
stdout
copy 
Case #1:
2
Case #2:
0
Case #3:
3
https://ideone.com/Oac4hQ
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!