CareerCup

trie datastructure

class SuffixTree implements String_DB{
	Node root;
	ArrayList<String> search_result;
	ArrayList<String> search(String s){
		search_result = null;
		Node current = root;
		int index = 0;
		outter : while (current.child.size() != 0){ // until we get to a leaf
			char c = s.charAt(index); // what we are looking for right now 
			inner : for (int i = 0 ; i < current.child.size() ; i++){
				if (current.child.get(i).c == c){
					current = current.child.get(i);
					index++;
					break inner;
				}
				break outter;
			}
		}
		search_result = new ArrayList<String>();
		DFS-Visit(current);
		return result;
	}
	void DFS-Visit(Node current , String so_far){
		String so_far = so_far + current.c;
		if (current.child.size() == 0){
			search_result.add(so_far);
			return;
		}
		for (int i = 0 ; i < current.child.size() ; i++)
			DFS-Visit(current.child.get(i) , so_far);
		return;
	}
	void insert(String str){
		String s = str + "$";
		for (int i = s.length - 1 ; i >= 0 ; i--)
			insert_sub(s.subtring(i));
		return;
	}
	void insert_sub(String s){
		Node current = root;
		int index = 0;
		outter : while (current.child.size() != 0){ // until we get to a leaf
			char c = s.charAt(index); // what we are looking for right now 
			inner : for (int i = 0 ; i < current.child.size() ; i++){
				if (current.child.get(i).c == c){
					current = current.child.get(i);
					index++;
					break inner;
				}
				break outter;
			}
		}
		if (index == s.length() -1) // it's already in the trie
			return;
		while (index < s.length()){
			Node new = new Node(s.charAt(index));
			current.child.add(new);
			current = new;
			index++;
		}
		return;
	}
	class Node{
		ArrayList<Node> child;
		char c;
		public Node(char c){
			child = new ArrayList<Node>();
			this.c = c;
		}
	}
}

You may also use KMP string matching algorithm , if the length of the list is O(m) and the length of each string is O(n) , this will take O(m * n) and the insertion takes O(1)

ArrayList<String> list = new ArrayList<String>();
ArrayList<String> search(String p){
	ArrayList<String> result = new ArrayList<String>();
	int[] func = prefix_function(p);
	for (int i = 0 ; i < list.size() ; i++)
		if (KMP(list.get(i) , p , func))
			result.add(list.get(i));
	return result;
}

int[] prefix_function(String P){
	int q = 0;
	int[] func = new int[P.length];
	func[0] = 0;
	for (int i = 1 ; i < P.length ; i++){
		while (q > 0 && P[q] != P[i])
			q = func[q];
		if (P[q] == P[i])
			q++;
		func[i] = q;
	}
	return func;
}
boolean KMP(String T , String P , int[] func){
	int q = 0;
	for (int i = 0; i < T.length() ; i++){
		while (q > 0 && T[i] != P[q])
			q = func[q];
		if (T[i] == P[q])
			q++;
		if (q == P.length)
			return true;
	}
	return false;
}

Also take note that in the previous code , you have to convert string to char array in each of the methods : KMP and prefix_function

void insert(String s){
	list.add(s);
}