Untitled

package dataStructure;

import java.util.*;

// Doubly Linked List
class LL{
	class Node{
		int data;
		Node prev;
		Node next;
		Node (){
			prev = next = null;
		}
		Node (int val){
			data = val;
			prev = next = null;
		}
	}
	
	Node head;
	Node tail;
	public LL (){
		head = new Node();
		tail = new Node();
		connectNode(head, tail);
	}	
	public void connectNode(Node front, Node end){
		front.next = end;
		end.prev = front;
	}
	public void insertNode(Node front, Node p, Node end){
		connectNode(front, p);
		connectNode(p, end);
	}
	public void eraseNode(Node p){
		connectNode(p.prev, p.next);
	}	
	public boolean isEmpty(){
		return head.next == tail;
	}
	public void addFisrt(int val){
		Node p = new Node(val);
		insertNode(head, p, head.next);
	}
	public void addLast(int val){
		Node p = new Node(val);
		insertNode(tail.prev, p, tail);
	}
	
	public void printList(){
		Node cur = head.next;
		while (cur != null){
			System.out.print(cur.data+" ");
			cur = cur.next;
		}
		System.out.println();
	}
}

// TreeSet
class NodeTreeSet {
	int score;
	int ID;
	NodeTreeSet(int id, int s) {
		ID = id;
		score = s;
	}
}
class CmpNodeTreeSet implements Comparator<NodeTreeSet> {
	@Override
	public int compare(NodeTreeSet n1, NodeTreeSet n2) {
		if (n2.score != n1.score)
			return n1.score - n2.score;
		return n1.ID - n2.ID;
	}
}

// Heap
class NodeHeap {
	int score;
	NodeHeap(int s) {
		score = s;
	}
}
class CmpNodeHeap implements Comparator<NodeHeap> {
	@Override
	public int compare(NodeHeap n1, NodeHeap n2) {
		return n2.score - n1.score;
	}
}

// DisjoinSet
class DisjoinSet{
	int[] parent;
	int N;
	public DisjoinSet(int n){
		parent = new int[n];
		this.N = n;
		makeset();
	}
	void makeset(){
		for (int i = 0; i < N; i++) parent[i] = i;
	}
	int findset(int x){
		if (parent[x] != x) parent[x] = findset(parent[x]);
		return parent[x];
	}
	void unionset(int x, int y){
		int preX = findset(x);
		int preY = findset(y);
		parent[preX] = preY;
	}
}

// Trie

class Trie{	
	class Node {
		static final int ALPHABET_SIZE = 26;
		Node[] children = new Node[ALPHABET_SIZE]; // ALPHABET_SIZE = 26
		boolean isLeaf;
		int count;
		Node() {
			for (int i = 0; i < ALPHABET_SIZE; i++) children[i] = null;
			count = 0;
			isLeaf = false;
		}		
	}
	
    static Node root;

	public Trie() {
		root = new Node();
	}
    
    void insert(String s){
        Node cur = root;      
        for (int c = 0; c < s.length(); c++){
        	int index = s.charAt(c) - 'a';
            if (cur.children[index] == null) 
            	cur.children[index] = new Node();
            cur = cur.children[index];
            cur.count++;
        }     
        cur.isLeaf = true;
    }
      
    int search(String s){
        Node cur = root;      
        for (int c = 0; c < s.length(); c++) {
        	int index = s.charAt(c) - 'a';      
            if (cur.children[index] == null) return 0;
            cur = cur.children[index];
        }
        return (cur.count);
    }
    
}

public class Main {
	// Linked List
	private static LL mList;
	// TreeSet
	private static TreeSet<NodeTreeSet> tree;
	private static TreeSet<NodeTreeSet>[] tree1d;
	private static TreeSet<NodeTreeSet>[][] tree2d;	
	// Heap
	private static PriorityQueue<NodeHeap> p;	
	// DisjointSet
	private static DisjoinSet djset;
	
	
	public void main(String[] args) {
		/* Linked List */
//		mList = new LL();
//		mList.addFisrt(3);
//		mList.addFisrt(2);
//		mList.addFisrt(1);
//		mList.printList();		
		/* TreeSet */
//		tree = new TreeSet<NodeTreeSet>(new CmpNodeTreeSet());
//		tree1d = new TreeSet[4];
//		tree2d = new TreeSet[4][3];
//		for (int i = 0; i < 4; i++){
//			tree1d[i] = new TreeSet<NodeTreeSet>(new CmpNodeTreeSet());
//			for (int j = 0; j < 3; j++){
//				tree2d[i][j] = new TreeSet<NodeTreeSet>(new CmpNodeTreeSet());
//			}
//		}	
		/* Heap */
//		p = new PriorityQueue<NodeHeap>(new CmpNodeHeap());
//		NodeHeap n1 = new NodeHeap(22);
//		NodeHeap n2 = new NodeHeap(88);
//		NodeHeap n3 = new NodeHeap(33);
//		NodeHeap n4 = new NodeHeap(77);
//		p.add(n1);
//		p.add(n2);
//		p.add(n3);
//		p.add(n4);
//		NodeHeap tp = p.peek();
//		tp = p.poll();
//		System.out.println(tp.score + "  " + p.size());	
		/* DisjointSet */
//		djset = new DisjoinSet(5);
//		djset.unionset(1, 2); // 1 is a friend of 2
//		djset.unionset(3, 4);
//		djset.unionset(4, 5);
//		if (djset.findset(4) == djset.findset(1)) 
//			System.out.println("ok");
//		else System.out.println("no");
	
		/* Trie */
		Trie t = new Trie();
		t.insert("abc");
		t.insert("abcd");
		t.insert("abd");
		t.insert("ace");
		System.out.println(t.search("ab"));
		
		
	}
	
}