原題：http://acm.hdu.edu.cn/showproblem.php?pid=1671

Time Limit: 3000/1000 MS (Java/Others)??? Memory Limit: 32768/32768 K (Java/Others)
Problem Description
Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let’s say the phone catalogue listed these numbers:
1. Emergency 911
2. Alice 97 625 999
3. Bob 91 12 54 26
In this case, it’s not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob’s phone number. So this list would not be consistent.
?

Input
The first line of input gives a single integer, 1 <= t <= 40, the number of test cases. Each test case starts with n, the number of phone numbers, on a separate line, 1 <= n <= 10000. Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.
?

Output
For each test case, output “YES” if the list is consistent, or “NO” otherwise.
?

Sample Input
2
3
911
97625999
91125426
5
113
12340
123440
12345
98346
?

Sample Output
NO
YES

分析：
這題和"統計帶某個前綴的單詞數量 "(HDOJ#1251)類似，也是用前綴樹。不過本題對內存的要求比較高（32768K），所以需要優化key值的存儲方式，而不能簡單地用String類型了。

由于字母表對應0..9共十個數字， 又有2^3 < 10 < 2^4，因此可以考慮用4個bits存儲一個數字。但是計算機中最小的存儲單元是字節，因此一個字節需要存儲兩個數字，同時還要考慮數字個數不為偶數的情 況，如果數字個數為奇數,那么有一個字節中另外4 bits沒有用來存儲數字，缺省時它的值等于0，但是0跟電話號碼中的數字0又會混淆，解決辦法是用0xF作為padding區分（因為數字0..9跟 0xF不相同）。因此設計這樣的壓縮存儲方式：
1）如果一個Trie結點中數字個數為偶數，不需要padding。
2）如果結點中數字個數為奇數，那么在存儲的第一個字節中前4位用來做padding，而且padding值為0xF。

代碼：

import java.util.LinkedList; import java.util.List; import java.util.Scanner;/*** * http://acm.hdu.edu.cn/showproblem.php?pid=1671* * @author ljs* 2011-06**/ public class Main {private class PatriciaTrieNode {private byte[] key;//1111-xxxx-xxxx-xxxx(e.g. 234) or xxxx-xxxx-xxxx-xxxx(e.g. 1234)private List<PatriciaTrieNode> children = new LinkedList<PatriciaTrieNode>();//use "#" for terminal charprivate boolean terminal; public PatriciaTrieNode(){ key = new byte[0];}public PatriciaTrieNode(byte[] key){this.key = packing(key); } //parameter key is in unpacked form;//return the packed formprivate byte[] packing(byte[] key){byte[] result = null;if(key.length %2 == 0){//no paddingresult = new byte[key.length/2];for(int i=0,j=0;i<key.length;i+=2,j++){result[j] = (byte)((((key[i] & 0x0F) << 4)+ (key[i+1] & 0x0F)) & 0x0FF);}}else{//with paddingresult = new byte[(key.length+1)/2];result[0] = (byte)(((0x0F << 4) + (key[0] & 0x0F)) & 0x0FF);for(int i=1,j=1;i<key.length;i+=2,j++){result[j] = (byte)((((key[i] & 0x0F) << 4)+ (key[i+1] & 0x0F)) & 0x0FF);}} return result;}//parameter key is in packed form//return the unpacked formprivate byte[] unpacking(byte[] key){boolean hasPadding = ((key[0] & 0x0F0) == 0x0F0);//1111-xxxx-byte[] result = null;if(hasPadding){result = new byte[key.length*2 - 1];result[0] = (byte)(key[0] & 0x0F);for(int i=1,j=1;i<key.length;i++,j+=2){result[j] = (byte)(((key[i] & 0x0F0) >> 4) & 0x0F);result[j+1] = (byte)(key[i] & 0x0F);}}else{result = new byte[key.length*2];for(int i=0,j=0;i<key.length;i++,j+=2){result[j] = (byte)(((key[i] & 0x0F0) >> 4) & 0x0F);result[j+1] = (byte)(key[i] & 0x0F);}}return result;}//get the number of real keys (when in unpacked form)public int getKeyLength(){ int childkeyLen = key.length*2;if((key[0] & 0x0F0) == 0x0F0){ childkeyLen--;}return childkeyLen;}//return the real key at position idx public byte getKey(int idx){if((key[0] & 0x0F0) != 0x0F0){if(idx%2 == 0)return (byte)(((key[idx/2] & 0x0F0) >> 4) & 0x0F);elsereturn (byte)(key[idx/2] & 0x0F);}else{if(idx%2 == 0)return (byte)(key[(idx+1)/2] & 0x0F);elsereturn (byte)(((key[(idx+1)/2] & 0x0F0) >> 4) & 0x0F); }} //return the suffix(right) in unpacked form public byte[] splitKeyAt(int idx){byte[] temp = this.unpacking(this.key);byte[] left = new byte[idx];byte[] right = new byte[temp.length-idx];System.arraycopy(temp, 0, left, 0, idx);System.arraycopy(temp, idx, right, 0, temp.length-idx);this.key = this.packing(left);return right;}public String toString(){ byte[] result = this.unpacking(key);StringBuilder sb = new StringBuilder();for(int k=0;k<result.length;k++){sb.append(String.valueOf(result[k]));}return sb.toString() + (this.terminal?"#":"") + "(" + children.size() +")";}}private PatriciaTrieNode root;private void insert(PatriciaTrieNode currNode,byte[] key) throws Exception{ boolean done = false;for(int i=0;i<currNode.children.size();i++){PatriciaTrieNode child = currNode.children.get(i);int childKeyLength = child.getKeyLength();int len = childKeyLength<key.length?childKeyLength:key.length;int j = 0;for(;j<len;j++){if(key[j] != child.getKey(j)){break;}}if(j==0){//this child doesn't match any character with the new key //order keys by lexi-orderif(key[0]<child.getKey(0)){//e.g. child="e" (currNode="abc")// abc abc// / \ =========> / | \// e f insert "c" c# e fPatriciaTrieNode node = new PatriciaTrieNode(key);currNode.children.add(i,node);node.terminal = true; done = true;break; }else{ //key.charAt(0)>child.key.charAt(0)//don't forget to add the largest new key after iterating all childrencontinue;}}else{//current child's key partially matches with the new key; 0<j<=len if(j==len){if(key.length==childKeyLength){if(child.terminal){throw new Exception("Duplicate Key is found when insertion!"); }else{//e.g. child="ab"// ab ab#// / \ =========> / \// e f insert "ab" e fchild.terminal = true;}}else if(key.length>childKeyLength){//e.g. child="ab#"// ab# ab#// / \ ==========> / | \ // e f insert "abc" c# e f //String subkey = key.substring(j);byte[] subkey = new byte[key.length - j];System.arraycopy(key, j, subkey, 0, key.length - j);//recursioninsert(child,subkey);}else{ //key.length()<child.key.length()//e.g. child="abc#"// abc# ab#// / \ =========> / // e f insert "ab" c# // / \// e f //String childSubkey = child.key.substring(j); //cbyte[] childSubkey = child.splitKeyAt(j);PatriciaTrieNode subChildNode = new PatriciaTrieNode(childSubkey);subChildNode.terminal = child.terminal;subChildNode.children = child.children; //inherited from parent//child.key = key; //abchild.terminal = true; //ab# child.children = new LinkedList<PatriciaTrieNode>();child.children.add(subChildNode);} }else{//0<j<len//e.g. child="abc#"// abc# ab// / \ ==========> / \// e f insert "abd" c# d# // / \// e f //split at j//String childSubkey = child.key.substring(j); //c//String subkey = key.substring(j); //dbyte[] childSubkey = child.splitKeyAt(j);byte[] subkey = new byte[key.length - j];System.arraycopy(key, j, subkey, 0, key.length - j);PatriciaTrieNode subChildNode = new PatriciaTrieNode(childSubkey);subChildNode.terminal = child.terminal;subChildNode.children = child.children; //inherited from parent//update child's key //child.key = child.key.substring(0,j);//child is not terminal now due to split, it is inherited by subChildNodechild.terminal = false;//Note: no need to merge subChildNode PatriciaTrieNode node = new PatriciaTrieNode(subkey);node.terminal = true;child.children = new LinkedList<PatriciaTrieNode>();if(subkey[0]<childSubkey[0]){child.children.add(node);child.children.add(subChildNode);}else{child.children.add(subChildNode);child.children.add(node);}}done = true;break;}}if(!done){PatriciaTrieNode node = new PatriciaTrieNode(key); node.terminal = true;currNode.children.add(node);}}public void insert(byte[] key) throws Exception{if(key == null || key.length == 0) return;if(root==null){root = new PatriciaTrieNode(); }insert(root,key); }private boolean traverse(PatriciaTrieNode currNode){boolean isConsistent = true;for(int i=0;i<currNode.children.size();i++){PatriciaTrieNode child = currNode.children.get(i);if(child.terminal){if(child.children.size()>0){isConsistent = false;break;}}else{isConsistent = traverse(child);if(!isConsistent){break;}}}return isConsistent;}public boolean traverse(){return traverse(this.root);}//for test purpose onlypublic void printTree(){this.print(0, this.root);}private void print(int level, PatriciaTrieNode node){for (int i = 0; i < level; i++) {System.out.format(" ");}System.out.format("|");for (int i = 0; i < level; i++) {System.out.format("-");}StringBuilder sb = new StringBuilder();if(node.key.length>0){byte[] result = node.unpacking(node.key); for(int k=0;k<result.length;k++){sb.append(String.valueOf(result[k]));}}if (node.terminal)System.out.format("%s#%n", sb.toString()); elseSystem.out.format("%s%n", sb.toString());for (PatriciaTrieNode child : node.children) {print(level + 1, child);} }public static void main(String[] args) {Scanner cin = new Scanner(System.in);String line = cin.nextLine();line = line.trim();int testCasesNum = Integer.parseInt(line);String[][] testCases = new String[testCasesNum][];for (int i = 0; i < testCasesNum; i++) {line = cin.nextLine();line = line.trim();int phoneNum = Integer.parseInt(line);String[] phones =new String[phoneNum];for(int j=0;j<phoneNum;j++){line = cin.nextLine();line = line.trim();phones[j] = line;}testCases[i] = phones;}for(int i=0;i<testCasesNum;i++){String[] phones = testCases[i];Main main = new Main();for (int j = 0; j < phones.length; j++) {try {byte[] phoneArr = new byte[phones[j].length()];for(int k=0;k<phones[j].length();k++){phoneArr[k] = (byte)(phones[j].charAt(k)-'0');}main.insert(phoneArr);} catch (Exception e) {}}//main.printTree();boolean consistent = main.traverse();if(consistent){System.out.println("YES");}else{System.out.println("NO");}}}}

#END#

轉載于:https://www.cnblogs.com/ljsspace/archive/2011/06/28/2092797.html

總結

以上是生活随笔為你收集整理的AC解 - Phone List(HDOJ#1671) 前缀树的一个应用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。