fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3. import java.math.*;
  4.  
  5. import static java.lang.Math.*;
  6. import static java.lang.Character.*;
  7. import static java.util.Arrays.*;
  8. import static java.util.Collections.*;
  9. import static java.math.BigInteger.*;
  10.  
  11. class B2 {
  12. 	static final char PROB = B2.class.getSimpleName().charAt(0);
  13. 	static final boolean PRAC = true;
  14.  
  15. 	static final int INF = 1 << 20;
  16. 	static final int[] di = { -1, 0, 0, 1 };
  17. 	static final int[] dj = { 0, -1, 1, 0 };
  18. 	static Scanner sc = new Scanner(System.in);
  19.  
  20. 	final int N, M;
  21. 	final char[][] D;
  22. 	final char[][] L;
  23.  
  24. 	int maxID;
  25.  
  26. 	public B2() {
  27. 		N = sc.nextInt();
  28. 		M = sc.nextInt();
  29. 		D = new char[N][];
  30. 		for (int i = 0; i < N; i++)
  31. 			D[i] = sc.next().toCharArray();
  32. 		L = new char[M][];
  33. 		for (int i = 0; i < M; i++)
  34. 			L[i] = sc.next().toCharArray();
  35. 	}
  36.  
  37. 	public String solve() {
  38. 		int[][] mask = new int[N][26];
  39. 		for (int i = 0; i < N; i++)
  40. 			for (int j = 0; j < 26; j++) {
  41. 				char c = (char) ('a' + j);
  42. 				for (int k = 0; k < D[i].length; k++)
  43. 					if (D[i][k] == c)
  44. 						mask[i][j] |= 1 << k;
  45. 			}
  46. 		StringBuilder sb = new StringBuilder();
  47. 		for (int k = 0; k < M; k++) {
  48. 			if (k > 0)
  49. 				sb.append(' ');
  50. 			int[][] is = new int[N][27];
  51. 			for (int i = 0; i < N; i++) {
  52. 				is[i][0] = D[i].length;
  53. 				for (int j = 0; j < 26; j++)
  54. 					is[i][j + 1] = mask[i][L[k][j] - 'a'];
  55. 			}
  56. 			Dic[] dics = new Dic[N];
  57. 			for (int i = 0; i < N; i++)
  58. 				dics[i] = new Dic(is[i], i);
  59. 			sort(dics);
  60. 			maxID = 0;
  61. 			dfs(dics, 0, 0, N);
  62. //			debug(dfs(dics, 0, 0, N), maxID);
  63. 			sb.append(D[maxID]);
  64. 		}
  65. 		return sb.toString();
  66. 	}
  67.  
  68. 	int dfs(Dic[] dics, int idx, int from, int to) {
  69. 		if (to - from == 1) {
  70. 			maxID = dics[from].idx;
  71. 			return 0;
  72. 		}
  73. 		boolean check = false;
  74. 		for (int i = from; i < to; i++)
  75. 			check |= dics[i].pat[idx] > 0;
  76.  
  77. 		int max = -1, id = from;
  78. 		for (int i = from, j = i + 1; i < to; i = j, j++) {
  79. 			while (j < to && dics[i].pat[idx] == dics[j].pat[idx])
  80. 				j++;
  81. 			int h = dfs(dics, idx + 1, i, j) + (check && dics[i].pat[idx] == 0 ? 1 : 0);
  82. 			if (h > max || (h == max && id > maxID)) {
  83. 				max = h;
  84. 				id = maxID;
  85. 			}
  86. 		}
  87. 		maxID = id;
  88. //		debug(idx, from, to, max, maxID);
  89. 		return max;
  90. 	}
  91.  
  92. 	private class Dic implements Comparable<Dic> {
  93. 		final int[] pat;
  94. 		final int idx;
  95.  
  96. 		public Dic(int[] pat, int idx) {
  97. 			this.pat = pat;
  98. 			this.idx = idx;
  99. 		}
  100.  
  101. 		@Override
  102. 		public int compareTo(Dic o) {
  103. 			for (int i = 0; i < 27; i++)
  104. 				if (pat[i] != o.pat[i])
  105. 					return pat[i] - o.pat[i];
  106. 			return idx - o.idx;
  107. 		}
  108. 	}
  109.  
  110. 	public static void main(String... args) {
  111. 		// large();
  112. 		int T = Integer.parseInt(sc.nextLine());
  113. 		for (int t = 1; t <= T; t++) {
  114. 			System.err.printf("Case #%s%n", t);
  115. 			System.out.printf("Case #%s: %s%n", t, new B2().solve());
  116. 		}
  117. 		System.err.println("done.");
  118. 	}
  119.  
  120. 	public static void small() {
  121. 		String in = PROB + "-small" + (PRAC ? "-practice" : "-attempt" + 0) + ".in";
  122. 		String out = PROB + "-small.out";
  123. 		try {
  124. 			if (!PRAC)
  125. 				for (int i = 1; new File(PROB + "-small" + "-attempt" + i + ".in").exists(); i++)
  126. 					in = PROB + "-small" + "-attempt" + i + ".in";
  127. 			System.setIn(new BufferedInputStream(new FileInputStream(in)));
  128. 			System.setOut(new PrintStream(out));
  129. 		} catch (Exception e) {
  130. 			e.printStackTrace();
  131. 			System.exit(0);
  132. 		}
  133. 		sc = new Scanner(System.in);
  134. 	}
  135.  
  136. 	public static void large() {
  137. 		String in = PROB + "-large" + (PRAC ? "-practice" : "") + ".in";
  138. 		String out = PROB + "-large.out";
  139. 		try {
  140. 			System.setIn(new BufferedInputStream(new FileInputStream(in)));
  141. 			System.setOut(new PrintStream(out));
  142. 		} catch (Exception e) {
  143. 			e.printStackTrace();
  144. 			System.exit(0);
  145. 		}
  146. 		sc = new Scanner(System.in);
  147. 	}
  148.  
  149. 	private static void debug(Object... os) {
  150. 		System.err.println(deepToString(os));
  151. 	}
  152. }
  153.  
Success #stdin #stdout 0.08s 213824KB
comments (?)
stdin
copy 
2
3 2
banana
caravan
pajamas
abcdefghijklmnopqrstuvwxyz
etaoisnhrdlcumwfgypbvkjxqz
4 1
potato
tomato
garlic
pepper
zyxwvutsrqponmlkjihgfedcba
stdout
copy 
Case #1: pajamas caravan
Case #2: garlic
https://ideone.com/SmVPY
language:
Java (HotSpot 12)
created:
12 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!