/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package XXXX;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.StringTokenizer;

/**
 *
 * @author poochedi
 */
public class CommonSubSequence {

    static HashMap table = new HashMap();

    public static void main(String[] args) throws IOException {

        InputStreamReader iReader = new InputStreamReader(System.in);
        BufferedReader bReader = new BufferedReader(iReader);
        ArrayList seqA = new ArrayList();
        ArrayList seqB = new ArrayList();
        ArrayList lngIncSeq = new ArrayList();
        System.out.println("Enter a sequence of numbers seperated by space Hit enter to terminate");
        String seqString = bReader.readLine();
        if(seqString != null) {

            StringTokenizer tokenizer = new StringTokenizer(seqString);
            while(tokenizer.hasMoreTokens()) {

                seqA.add(tokenizer.nextToken());
            }
            System.out.println("seqList " + seqA.toString());
        }
        else
            System.out.println("No sequence");

        System.out.println("Enter a sequence of numbers seperated by space Hit enter to terminate");
        seqString = bReader.readLine();
        if(seqString != null) {

            StringTokenizer tokenizer = new StringTokenizer(seqString);
            while(tokenizer.hasMoreTokens()) {

                seqB.add(tokenizer.nextToken());
            }
            System.out.println("seqList " + seqB.toString());
        }
        else
            System.out.println("No sequence");

        //compare seqA and seqB
        if(seqA.size() < seqB.size()){

            //enter elements of B to hashtable and compare them with the smaller list,seqA
            fillTable(seqB);
            compare(seqA);
        }
        else {
            //seqA will get into hashtable and is compared with the smaller list seqB
            fillTable(seqA);
            compare(seqB);
        }    

    }

    public static void fillTable(ArrayList list) {

        Iterator listItr = list.iterator();
        while(listItr.hasNext()) {

            table.put(Integer.parseInt(listItr.next().toString()), 0);
        }
     }

    public static void compare(ArrayList list) {

        int tableLookup = 0;
        //for each element in the list lookup whether its in the list
        //if so set the elements val = 1.
        //finally print the elements in the table with val = 1. they are the elements common to both
        Iterator listItr = list.iterator();
        while(listItr.hasNext()) {

            int elt =  Integer.parseInt((String)(listItr.next()));
            System.out.println("elt " + elt);
             if(table.get(elt) != null) {

                 tableLookup = (int) table.get(elt);
                 table.put(elt, 1); //this elt matches
             }
        }

        System.out.println("Printing the common elements");
        //get the set of entries
        Set set = table.entrySet();
        //get an iterator
        Iterator itr = set.iterator();
        while(itr.hasNext()) {

            Map.Entry elt = (Map.Entry)itr.next();
            if(elt.getValue() == 1){
                System.out.println(elt.getKey());
            }
        }
    }
}
Advertisements