Can't get this java code to run faster

Question

I'm participating in an online judge page, where I solved a problem, but I just can't make my program run in time. The code is as follows:

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
Set l = new HashSet();
String line;
String[] numStr;
 while(true){
  line = in.readLine();      
  numStr = line.split("\\s");      
  int a = Integer.parseInt(numStr[0]);
  if(a == 0){
     System.exit(0);
  }
  int n = 0;
  int b = Integer.parseInt(numStr[1]);
  l.clear();
  for(int i=0;i<a;i++){
    l.add(in.readLine());
  }
  for(int i=0;i<b;i++){
    if(l.contains(in.readLine())){
      n++;
    }
  }
  System.out.println(n);

I came to a point where for a test case of 2 million items (numStr = "1000000 1000000") I got it to run under 1.5s, but apparently that's not enough for the test cases (it says 3000ms). And now I don't know how can I make it faster, any help is greatly appreciated!

Problem: http://coj.uci.cu/24h/problem.xhtml?abb=1438

Answer 1

The "in increasing order" part of the input specification is the key: since both lists are pre-sorted, you can read the first one into an array, and then use binary search from the location of the last item to the end of the array to decide if you have a match or not. In fact, even a linear search of the first array might work, because you will need to traverse it at most once.