summaryrefslogtreecommitdiff
path: root/src/main
diff options
context:
space:
mode:
Diffstat (limited to 'src/main')
-rw-r--r--src/main/HashChains.java125
1 files changed, 125 insertions, 0 deletions
diff --git a/src/main/HashChains.java b/src/main/HashChains.java
new file mode 100644
index 0000000..f21d05d
--- /dev/null
+++ b/src/main/HashChains.java
@@ -0,0 +1,125 @@
+import java.io.*;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.StringTokenizer;
+
+public class HashChains {
+
+ private FastScanner in;
+ private PrintWriter out;
+ // store all strings in one list
+ private List<List<String>> elems;
+ // for hash function
+ int bucketCount;
+
+ public static void main(String[] args) throws IOException {
+ new HashChains().processQueries();
+ }
+
+ int hashFunc(String s) {
+ long hash = 0;
+ int prime = 1000000007;
+ int multiplier = 263;
+ for (int i = s.length() - 1; i >= 0; --i)
+ hash = (hash * multiplier + s.charAt(i)) % prime;
+ return (int) hash % bucketCount;
+ }
+
+ private Query readQuery() throws IOException {
+ String type = in.next();
+ if (!type.equals("check")) {
+ String s = in.next();
+ return new Query(type, s);
+ } else {
+ int ind = in.nextInt();
+ return new Query(type, ind);
+ }
+ }
+
+ private void writeSearchResult(boolean wasFound) {
+ out.println(wasFound ? "yes" : "no");
+ // Uncomment the following if you want to play with the program interactively.
+ // out.flush();
+ }
+
+ private void processQuery(Query query) {
+ int hashIndex;
+ switch (query.type) {
+ case "add":
+ hashIndex = hashFunc(query.s);
+ if (!elems.get(hashIndex).contains(query.s))
+ elems.get(hashIndex).add(0, query.s);
+ break;
+ case "del":
+ hashIndex = hashFunc(query.s);
+ elems.get(hashIndex).remove(query.s);
+ break;
+ case "find":
+ hashIndex = hashFunc(query.s);
+ writeSearchResult(elems.get(hashIndex).contains(query.s));
+ break;
+ case "check":
+ for (String cur : elems.get(query.ind))
+ out.print(cur + " ");
+ out.println();
+ // Uncomment the following if you want to play with the program interactively.
+ // out.flush();
+ break;
+ default:
+ throw new RuntimeException("Unknown query: " + query.type);
+ }
+ }
+
+ private void processQueries() throws IOException {
+ elems = new ArrayList<>();
+ in = new FastScanner();
+ out = new PrintWriter(new BufferedOutputStream(System.out));
+ bucketCount = in.nextInt();
+ for (int i = 0; i < bucketCount; i++) {
+ elems.add(new ArrayList<>());
+ }
+ int queryCount = in.nextInt();
+ for (int i = 0; i < queryCount; ++i) {
+ processQuery(readQuery());
+ }
+ out.close();
+ }
+
+ static class Query {
+ String type;
+ String s;
+ int ind;
+
+ Query(String type, String s) {
+ this.type = type;
+ this.s = s;
+ }
+
+ Query(String type, int ind) {
+ this.type = type;
+ this.ind = ind;
+ }
+ }
+
+ static class FastScanner {
+ private BufferedReader reader;
+ private StringTokenizer tokenizer;
+
+ FastScanner() {
+ reader = new BufferedReader(new InputStreamReader(System.in));
+ tokenizer = null;
+ }
+
+ String next() throws IOException {
+ while (tokenizer == null || !tokenizer.hasMoreTokens()) {
+ tokenizer = new StringTokenizer(reader.readLine());
+ }
+ return tokenizer.nextToken();
+ }
+
+ int nextInt() throws IOException {
+ return Integer.parseInt(next());
+ }
+ }
+}
+