0811-2 求最小前缀

给以文件，文件中每一行是一个单词，求出每个单词的最小前缀，使得该最小前缀能够代表这个单词。(当没有任何其他单词与之有共同的该前缀，该前缀就是最小前缀了。)

例如：

输入文件为：

cat

catt

cbtd

batty

abttyy

 

那么应该输出：

[前缀]   [单词]   

 cat      cat

 catt     catt

 cb       cbtd

 b        batty

 a        abttyy

 

 

 

编写代码时遇到了ConcurrentModificationException 异常，解决方法参考：http://61234865.iteye.com/category/98984?show_full=true

 

原理参考：

               http://www.iteye.com/topic/656670

               http://www.iteye.com/topic/164644

               http://www.iteye.com/topic/344876

               http://www.blogjava.net/houlinyan/archive/2008/04/01.html

               http://hi.baidu.com/latte88/blog/item/598b1e38d38366ced46225e1.html

 

 

 

这些原理看得很晕，现在只知道用ConcurrentHashMap代替HashMap可以解决该问题。

本文提供了代码下载，请高手用比较简单易懂的话告诉我原理吧。

 

package org.jyjiao;

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.io.*;

public class StrPre {
	public void getPrefix(String path){
		ConcurrentHashMap<String,String> map=new ConcurrentHashMap<String,String>();
		//HashMap<String,String> map=new HashMap<String,String>(); //这样会抛出ConcurrentModificationException 异常
		try{
			BufferedReader br=new BufferedReader(new FileReader(path));
			String str;
			String value;
			String key;
			int tag=0;
		
			while((str=br.readLine())!=null){
				key=str.substring(0,1);
				if(map.containsKey(key)){
					value=map.get(key);
					value+="|"+str;
				}else{
					value=str;					
				}
				map.put(key,value);	
				
			}
		  int len=2;
		  int flag=0;
		
		  Iterator it=map.entrySet().iterator();
		  while(true){
		  	
		  	while(it.hasNext()){
		  		
		  		Map.Entry me=(Map.Entry)it.next();
		  		String mKey=(String)me.getKey();
		  		String mValue=(String)me.getValue();
		  		String[] varray=mValue.split("\\|");  // 第二个\用于对|转义，第一个\用于对第二个\转义
		  		String keypre,valuepre;
		  		if(varray.length>1 &&(flag==0||(flag==1&&mKey.length()<len))){
		  			tag=1;
		  			flag=1;
		  			for(int i=0;i<varray.length;i++){
		  				
		  				if(varray[i].length()>=len){
		  					key=varray[i].substring(0,len);
		  					keypre=varray[i].substring(0,len-1);
		  					if(map.containsKey(key)){
		  						value=map.get(key);
		  						value+="|"+varray[i];
		  					}else{
		  						value=varray[i];
		  					}
		  					map.put(key,value);
		  					
		  					if(map.containsKey(keypre)){
		  						valuepre=map.get(keypre);
		  						int index1=valuepre.indexOf(varray[i]);
		  						int index2=valuepre.indexOf("|",index1);
		  						
		  						String pre=valuepre.substring(0,index1);
		  						String post;
		  						if(index2==-1){
		  							post="";
		  						}else{
		  							post=valuepre.substring(index2+1);
		  						}
		  						valuepre=pre+post;
		  						map.put(keypre,valuepre);						
		  					
		  					}
		  					
		  				}
		  			}
		  			keypre=varray[0].substring(0,len-1);
		  			String strt=(String)map.get(keypre);
		  		
		  			if(strt.length()==0){
		  				it.remove(); //安全的删除操作
		  				//map.remove(keypre);//不推荐的删除操作
		  						  				
		  			}
		  		}
		  		
		  	}
		  	
		  	if(tag==0){
		  		break;
		  	}
		  	it=map.entrySet().iterator();
		  	tag=0;
		  	flag=0;
		  	len++;
		  }
		  
		//  System.out.println(map);
		  
		  Iterator ret=map.entrySet().iterator();
		  while(ret.hasNext()){
		  		Map.Entry me1=(Map.Entry)ret.next();
		  		System.out.println(me1.getKey()+"    "+me1.getValue());
		  }
		  br.close();
		}catch(Exception ex){
			ex.printStackTrace();
		}
	}

	public static void main(String[] args) {
		StrPre strpre = new StrPre();
		strpre.getPrefix("C:/jtest/8/0811/word.txt");

	}
}