-
Notifications
You must be signed in to change notification settings - Fork 0
/
Trie.java
129 lines (103 loc) · 2.27 KB
/
Trie.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
package rsn170330.sp13;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Scanner;
/**
* Implementation of Data Structures and Algorithms Fall 2018
*
* Short Project SP13: String Algorithms
* Fri, Nov 30, 2018
*
* 1. Implement Tries. Starter code is provided. You may modify the methods and
* parameters (even for public methods), as needed.
*
* 2. Implement KMP algorithm. Use it to solve the following problem: Given a
* string s, find the shortest string x such that x + s is a palindrome.
*
* 3. Implement Boyer-Moore algorithm.
*
* 4. Implement automata matcher.
*
* @author Rahul Nalawade (rsn170330)
*
* @date December 16, 2018
*/
public class Trie<V> {
private class Entry {
V value;
HashMap<Character, Entry> child;
int depth;
Entry(V value, int depth) {
this.value = value;
child = new HashMap<>();
this.depth = depth;
}
}
private Entry root;
private int size;
public Trie() {
root = new Entry(null, 0);
size = 0;
}
private V put(Iterator<Character> iter, V value) {
return null;
}
private V get(Iterator<Character> iter) {
return null;
}
private V remove(Iterator<Character> iter) {
return null;
}
// public methods
public V put(String s, V value) {
return null;
}
public V get(String s) {
return null;
}
public V remove(String s) {
return null;
}
// How many words in the dictionary start with this prefix?
public int prefixCount(String s) {
return 0;
}
public int size() {
return size;
}
public static class StringIterator implements Iterator<Character> {
char[] arr;
int index;
public StringIterator(String s) {
arr = s.toCharArray();
index = 0;
}
public boolean hasNext() {
return index < arr.length;
}
public Character next() {
return arr[index++];
}
public void remove() {
throw new java.lang.UnsupportedOperationException();
}
}
public static void main(String[] args) {
Trie<Integer> trie = new Trie<>();
int wordno = 0;
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
String s = in.next();
if (s.equals("End")) {
break;
}
wordno++;
trie.put(s, wordno);
}
while (in.hasNext()) {
String s = in.next();
Integer val = trie.get(s);
System.out.println(s + "\t" + val);
}
}
}