-
Notifications
You must be signed in to change notification settings - Fork 0
/
F_TachXau.java
137 lines (119 loc) · 3.82 KB
/
F_TachXau.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
import java.io.*;
import java.nio.file.Files;
import java.util.*;
/**
* @author thucdx
*/
public class F_TachXau {
static boolean IS_LOCAL = System.getenv("LOCAL_JUDGE") != null;
static boolean DEBUG = IS_LOCAL & false;
static String INPUT_FILE = "input/F_Xau.inp";
static Set<String> dict;
static int[] start;
static boolean[] isOK;
static void solve(String phrase, BufferedWriter bw) throws IOException {
int l = phrase.length();
start = new int[l+1];
isOK = new boolean[l+1];
Arrays.fill(isOK, false);
Arrays.fill(start, -2);
debug("Phase", phrase);
for (int i = 0; i < l; i++) {
// isOK[i] ??
String cur = "";
for (int begin = i; begin >= 0; begin--) {
cur = phrase.charAt(begin) + cur;
if (dict.contains(cur)) {
if (begin == 0) {
isOK[i] = true;
start[i] = 0;
} else {
if (isOK[begin-1]) {
isOK[i] = true;
start[i] = begin;
break;
}
}
}
}
}
if (isOK[l-1]) {
int cur = l-1;
for (int i = 0; i < l; i++) {
debug(i, start[i]);
}
List<String> res = new ArrayList<>();
while (cur >= 0) {
String s = phrase.substring(start[cur], cur+1);
res.add(s);
debug(" => s", s, cur);
cur = start[cur]-1;
}
Collections.reverse(res);
for(String r: res) {
bw.write(r + " ");
}
bw.write("\n");
} else {
bw.write("-1\n");
}
}
public static void main(String[] args) {
try {
InputStream is = IS_LOCAL ? Files.newInputStream(new File(INPUT_FILE).toPath()) : System.in;
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
InputReader ir = new InputReader(is);
// Process here!
int nDict = ir.nextInt();
dict = new HashSet<>();
for (int i = 0; i < nDict; i++) {
String word = ir.next();
dict.add(word);
// debug(word);
}
int nCase = ir.nextInt();
for (int i = 0; i < nCase; i++) {
String phrase = ir.next();
solve(phrase, bw);
}
bw.flush();
} catch (Exception ex) {
ex.printStackTrace();
}
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
public double nextDouble() {
return Double.parseDouble(next());
}
}
static void debug(Object... args) {
if (DEBUG) {
for (int i = 0; i < args.length; ++i) {
System.out.print(args[i] + " ");
}
System.out.println();
}
}
}