poj 2001 解题报告

import java.util.Scanner;

public class Main {
	private static Trie trie = new Trie();

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String[] str = new String[1002];
		int sum = 0;
		while (sc.hasNext()) {
			String s = sc.nextLine();
			str[sum++] = s;
			insertTrie(s);
		}

		for (int i = 0; i < sum; ++i) {
			System.out.println(str[i] + " "
					+ str[i].substring(0, searchPrefix(str[i]) + 1));
		}
	}

	private static int searchPrefix(String s) {

		int len = s.length();
		Trie root = trie;
		for (int i = 0; i < len; ++i) {
			int c = s.charAt(i) - 'a';
			if (root.next[c].node == 1)
				return i;
			root = root.next[c];
		}
		return s.length() - 1;
	}

	private static void insertTrie(String s) {
		int len = s.length();
		Trie root = trie;
		for (int i = 0; i < len; ++i) {
			int c = s.charAt(i) - 'a';
			Trie node = root.next[c];
			if (node == null) {
				node = new Trie();
				root.next[c] = node;
			}
			root.next[c].node++;
			root = root.next[c];
		}
	}

	private static class Trie {
		private int node = 0;
		private Trie[] next = new Trie[26];
	}
}

poj2001 求一个字符串在一个字符串集中的唯一最短前缀，典型的Trie树，一次AC，粗心把语言选择成g++了编译错误一次，呵呵！杯具。。。