/** * poj 2001 * trie字典树 * 題意:给出n个单词(1<=n<=1000),求出每个单词的非公共前缀,如果没有,则输出自己。 */ import java.util.*; class Node { int num; Node[] child = new Node[26]; } public class Main { final int MAX = 1005; Scanner sc = new Scanner(System.in); char[][] str = new char[MAX][21]; Node root = new Node(); void insert(char[] s) { Node node = root; for (int i = 0; i < s.length; i++) { int id = s[i] - 'a'; if (node.child[id] == null) node.child[id] = new Node(); node = node.child[id]; node.num++; } } void find(char[] s) { Node node = root; System.out.print(new String(s) + " "); for (int i = 0; i < s.length; i++) { System.out.print(s[i]); int id = s[i] - 'a'; if (node.child[id].num == 1) break; node = node.child[id]; } System.out.println(); } void init() { char[] s = new char[21]; int index = 0; while (sc.hasNext()) { s = sc.next().toCharArray(); str[index++] = s; insert(s); } for (int i = 0; i < index; i++) { find(str[i]); } } public static void main(String[] args) throws Exception { new Main().init(); } }