プログラミングの美しさ-最短要約の生成

3646 ワード

package structure;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 
 *        :            ,  M     ,           ,       ;   N        ,
 *             String extractSummary(String description,String[] key words),
 *              N    (           )        ,        
 *   : w1,w2,q1,w3,w4,w5,q2,w6,w7,q1,w8,w9,w10              ,     q1,q2
 *   1             ,            ,          ,       ,               ,    
 */
public class ShortestSummary {
    String[] text; // = "hello world tst sepring sun flower hello";
    String[] keywords;// = { "hello", "world" };
    Map<String, Integer> map = new HashMap<String, Integer>();
    int[] count;

    public ShortestSummary(String[] text, String[] keywords) {
	this.text = text;
	this.keywords = keywords;
	count = new int[keywords.length];
	for (int i = 0, len = keywords.length; i < len; i++)
	    map.put(keywords[i], i);
    }
    /**
     *           text[]    ,      ,             ,       ,    
     *               , : text[] = {a a a b c d a} key {b d }
     * 	            :(        ){a a a b c d }     6
     *            (        ){a a b c d }	      5 
     *         (        ) {a b c d }	      4 
     *         (        ){b c d }		      3 
     *                     ,           
     *                      ,   {a a a b c d},from       ,to      ,from-to       ,    ,   from         ,
     *     [from+1 ,to]     [from,to]   ,         ,   from      ,[from+1,to]           ,       to   ,        
     *          from,to        ,           
     */
   /*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++   ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++=*/
    public void execute() {
	int start = 0, len = text.length, min = len;
	for (int i = 0; i < len; i++) {
	    int t = exec(i, len - 1);
	    if (t > -1)
		if (min > t) {
		    min = t;
		    start = i;
		}
	}
	for (int i = start; i <= start + min; i++)
	    System.out.print(text[i] + " ");

    }

    private int exec(int from, int to) {
	count = new int[keywords.length];
	int start = from;
	while (from <= to && !isAllgeted()) {
	    Integer i = map.get(text[from]);
	    if (i != null) {
		count[i]++;
	    }
	    from++;
	}
	if (isAllgeted())
	    return from - start - 1;
	return -1;
    }

    private boolean isAllgeted() {
	for (int i = 0, len = count.length; i < len; i++)
	    if (count[i] == 0)
		return false;
	return true;
    }
    /*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++   ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++=*/
    //      ,       
     void execute2(){
	int start = 0,end=0,min = text.length,len = text.length,targetStart = 0,targetEnd = len;
	while(true){
	    while(end<len && !isAllgeted()){
		Integer t  = map.get(text[end]);
		if(t !=null)
		    count[t]++;
		end++;
	    }	//      ,    
	    
	    while(isAllgeted() && start<=end){
		if(end-start<min){
		    min = end-start;
		    targetStart = start;
		    targetEnd = end;
		}
		Integer t = map.get(text[start]);
		if(t !=null)
		    count[t]--;
		start ++ ;
		
	    }
	   if(end>=len)break;
	  
	}
	for(int i=targetStart;i<targetEnd;i++)
	    System.out.print(text[i]+" ");
	
	
    }
    public static void main(String args[]) {
	String[] text = "hello software hello test world spring sun flower hello".split(" ");
	String[] keys = {"hello","world"};
	ShortestSummary s = new ShortestSummary(text, keys);
	s.execute2();
    }

}