HDU1247（字典树应用）

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1247

package D0726;//字典树import java.io.*;public class HDU1247 {static Trie2 root = new Trie2();public static void main(String[] args) throws IOException {StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));String str;String[] strarr = new String[50001];//保存得单词int index = 0;while(st.nextToken() != StreamTokenizer.TT_EOF){str = st.sval;strarr[index++] = str;insert(str);//if(index==5)break;}//查找for(int i = 0;i<index;i++){if(find(strarr[i]))//System.out.println(strarr[i]);out.println(strarr[i]);}out.flush();}private static boolean find(String string) {Trie2 cur = root;for(int k = 0;k<string.length();k++){char ch = string.charAt(k);int idx = ch - 'a';cur = cur.child[idx];if(cur != null){if(cur.i==1&&find2(string.substring(k+1)))return true;}else return false;}return false;}private static boolean find2(String string) {Trie2 cur = root;for(int k = 0;k<string.length();k++){char ch = string.charAt(k);int idx = ch - 'a';if(cur.child[idx] != null){cur = cur.child[idx];if(cur.i==1&&k==(string.length()-1))//这个条件很重要，一定要比较到结尾return true;}else return false;}return false;}//构建字典树public static void insert(String str){Trie2 cur = root;for(char ch: str.toCharArray()){int idx = ch-'a';if (cur.child[idx] == null) {cur.child[idx] = new Trie2();cur = cur.child[idx];}else cur = cur.child[idx];}cur.i = 1;}}//字典树class Trie2{Trie2[] child;int i;public Trie2(){child = new Trie2[26];}}