Advertisement
Guest User

Untitled

a guest
Nov 12th, 2012
116
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.51 KB | None | 0 0
  1. package stringProblems;
  2.  
  3. import java.io.*;
  4. import java.util.HashMap;
  5.  
  6.  class Subsequence3 {
  7.  
  8.      static boolean containsAll (HashMap<Integer,String> lookup,String[] tokens)
  9.      {  boolean found=true;
  10.          for(int i=0;i<tokens.length;i++)
  11.                 if(!lookup.containsValue(tokens[i]))
  12.                    found=false;
  13.     return found;
  14.      }
  15.     public static void main(String[] args)
  16.     {
  17.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  18.        
  19.         try{
  20.               String input=br.readLine();
  21.               String res= input.replaceAll("[^a-zA-Z]"," " );
  22.               String[] AlltokensInput=res.split("\\s+");
  23.               int N=AlltokensInput.length;
  24.               String[] Alltokens=new String[N];
  25.               for(int i=0;i<N;i++)
  26.                   Alltokens[i]=AlltokensInput[i];
  27.                    //total number of strings in input line
  28.                 for(int i=0;i<N;i++)  //Alltokens is the input line
  29.                     Alltokens[i]=Alltokens[i].toLowerCase();
  30.             int k= Integer.parseInt(br.readLine());  //number of tokens to be searched in sub sequence of input line
  31.                String[] tokensInput=new String[k]; 
  32.                String[] tokens=tokensInput;
  33.                 for(int i=0;i<k;i++)
  34.                     {tokensInput[i]=br.readLine();
  35.                      tokens[i]=tokensInput[i].toLowerCase();
  36.                     }
  37.                
  38.             boolean found=false;      //Flag to indicate if all tokens have been found
  39.             boolean everFound=false;
  40.            
  41.             HashMap<Integer,String> lookup=new HashMap<Integer,String>();
  42.            
  43.            
  44.               for (int start=0;start<k;start++)
  45.               {                                      //build a HashSet of first k strings of input line.Minimun set which can contain k different tokens
  46.               lookup.put(start,Alltokens[start]);
  47.               }
  48.              
  49.               //Collection<String> tok=Arrays.asList(tokens); //collection of tokens to be found
  50.               //System.out.println("tokens are  "+tok.toString());
  51.              
  52.              
  53.               int minRange=0,maxRange=N;  //minimun interval which contains all tokens
  54.              
  55.               for(int min=0,max=k;min>=0&&max<N;)  //Start with first string in input,If tokens are not found.Add kth string in input and test
  56.                {
  57.                  if(found==false)
  58.                    {while(!containsAll(lookup,tokens)&&max<N)  //Minimum value of max for which min-max contains tok
  59.                        {
  60.                        lookup.put(max,Alltokens[max]);
  61.                       // System.out.println(" Increasing Max "+lookup.toString()+"  found ="+found);
  62.                        max++;
  63.                        }
  64.                        if(max<N)
  65.                            {found=true;
  66.                            everFound=true;
  67.                            }
  68.                        else
  69.                            {found=false;  
  70.                            if(everFound==false)
  71.                             {System.out.print("No subsegment found");
  72.                              System.exit(0);
  73.                              }                     
  74.                             }
  75.                      }
  76.                   else
  77.                    {       //If all tokens were found in 0-max ,strip off string[0] and test and so on for next min which would be 1
  78.                      lookup.remove(min);
  79.                       min++;
  80.                        if(!containsAll(lookup,tokens))  //Strip of min from the range min-max and test min+1 to max
  81.                           found=false;
  82.                        //System.out.println(" Increasing Min "+lookup.toString()+"  found = "+found);
  83.                      
  84.                      }
  85.                    
  86.               if(max-min<maxRange-minRange&&found==true)
  87.                    {minRange=min;
  88.                     maxRange=max;
  89.                     }
  90.                    
  91.                 }
  92.    
  93.          
  94.     //System.out.println("\n Minrange"+minRange+" Maxrange "+maxRange);
  95.     //System.out.println("Minimum subseqence is");
  96.     if(everFound==true)
  97.     for(int i=minRange;i<maxRange;i++)
  98.         System.out.print(AlltokensInput[i]+" ");
  99.  
  100.        
  101.         }
  102.         catch(IOException e){}
  103.     }
  104.    
  105. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement