Visits: 103

蒜头君作为蒜厂的工程师，在开发网站时不小心写出了一个 Bug：当用户输入密码时，如果既和自己的密码一致，也同时是另一个用户密码的 前缀 时，用户会跳转到 404 页。

然而蒜头君坚称：我们的用户那么少，怎么可能触发这个 Bug……

机智的你，能不能帮蒜头君确认一下这个 Bug 到底会不会触发呢？

输入格式

第一行输入一个整数 $n(1 \leq n \leq 233333)$，表示蒜厂网站的用户数。接下来一共 $n$ 行，每行一个由小写字母 a-z 组成的字符串，长度不超过 $10$，表示每个用户的密码。蒜厂的数据库容量太小，所有密码长度加起来小于 $466666$。

输出格式

如果触发了 Bug 则输出一行 Bug!，否则输出一行 Good Luck!。

样例 1

3
abc
abcdef
cdef

Bug!

样例2

3
abc
bcd
cde

Good Luck!

这题就是最单纯的前缀树模板。

对于先输入短的，后输入长的，就在遇到长的密码的每一个结点判断是不是 isEnd()，反之，则在 setEnd() 之后检查还有没有后面的孩子结点。

import java.util.HashMap;
import java.util.Scanner;

public class Main {

    static Scanner in = new Scanner(System.in);

    public static void main(String[] args) {
        Trie tree = new Trie();
        int n = in.nextInt();
        for (int i = 0; i < n; i++) {
            String s = in.next();
            try {
                tree.insert(s);
            } catch (Exception e) {
                System.out.println("Bug!");
                System.exit(0);
            }
        }
        System.out.println("Good Luck!");
    }

}

class Trie {

    private TrieNode root;

    /**
     * Initialize your data structure here.
     */
    public Trie() {
        root = new TrieNode();
    }

    /**
     * Inserts a word into the trie.
     */
    public void insert(String word) throws Exception {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (!node.contains(c)) {
                node.put(c);
            }
            node = node.get(c);
            if (node.isEnd()) {
                throw new Exception("BUG");
            }
        }
        node.setEnd();
        if (node.hasChild()) {
            throw new Exception("BUG");
        }
    }
}

class TrieNode {
    private HashMap<Character, TrieNode> links;
    private boolean end;

    public TrieNode() {
        links = new HashMap<>();
        end = false;
    }

    public boolean isEnd() {
        return end;
    }

    public void setEnd() {
        end = true;
    }

    public TrieNode get(char c) {
        return links.get(c);
    }

    public void put(char c) {
        links.put(c, new TrieNode());
    }

    public boolean contains(char c) {
        return links.containsKey(c);
    }

    public boolean hasChild() {
        return !links.keySet().isEmpty();
    }

}