Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package stringProblems;
- import java.io.*;
- import java.util.HashMap;
- class Subsequence3 {
- static boolean containsAll (HashMap<Integer,String> lookup,String[] tokens)
- { boolean found=true;
- for(int i=0;i<tokens.length;i++)
- if(!lookup.containsValue(tokens[i]))
- found=false;
- return found;
- }
- public static void main(String[] args)
- {
- BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
- try{
- String input=br.readLine();
- String res= input.replaceAll("[^a-zA-Z]"," " );
- String[] AlltokensInput=res.split("\\s+");
- int N=AlltokensInput.length;
- String[] Alltokens=new String[N];
- for(int i=0;i<N;i++)
- Alltokens[i]=AlltokensInput[i];
- //total number of strings in input line
- for(int i=0;i<N;i++) //Alltokens is the input line
- Alltokens[i]=Alltokens[i].toLowerCase();
- int k= Integer.parseInt(br.readLine()); //number of tokens to be searched in sub sequence of input line
- String[] tokensInput=new String[k];
- String[] tokens=tokensInput;
- for(int i=0;i<k;i++)
- {tokensInput[i]=br.readLine();
- tokens[i]=tokensInput[i].toLowerCase();
- }
- boolean found=false; //Flag to indicate if all tokens have been found
- boolean everFound=false;
- HashMap<Integer,String> lookup=new HashMap<Integer,String>();
- for (int start=0;start<k;start++)
- { //build a HashSet of first k strings of input line.Minimun set which can contain k different tokens
- lookup.put(start,Alltokens[start]);
- }
- //Collection<String> tok=Arrays.asList(tokens); //collection of tokens to be found
- //System.out.println("tokens are "+tok.toString());
- int minRange=0,maxRange=N; //minimun interval which contains all tokens
- 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
- {
- if(found==false)
- {while(!containsAll(lookup,tokens)&&max<N) //Minimum value of max for which min-max contains tok
- {
- lookup.put(max,Alltokens[max]);
- // System.out.println(" Increasing Max "+lookup.toString()+" found ="+found);
- max++;
- }
- if(max<N)
- {found=true;
- everFound=true;
- }
- else
- {found=false;
- if(everFound==false)
- {System.out.print("No subsegment found");
- System.exit(0);
- }
- }
- }
- else
- { //If all tokens were found in 0-max ,strip off string[0] and test and so on for next min which would be 1
- lookup.remove(min);
- min++;
- if(!containsAll(lookup,tokens)) //Strip of min from the range min-max and test min+1 to max
- found=false;
- //System.out.println(" Increasing Min "+lookup.toString()+" found = "+found);
- }
- if(max-min<maxRange-minRange&&found==true)
- {minRange=min;
- maxRange=max;
- }
- }
- //System.out.println("\n Minrange"+minRange+" Maxrange "+maxRange);
- //System.out.println("Minimum subseqence is");
- if(everFound==true)
- for(int i=minRange;i<maxRange;i++)
- System.out.print(AlltokensInput[i]+" ");
- }
- catch(IOException e){}
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement