UVA - 531 - Compromise

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb=new StringBuffer("");
        String m="";
        while((m=br.readLine())!=null){
            Queue<String> qu=new LinkedList<String>();
            while(true){
                StringTokenizer st=new StringTokenizer(m);
                int countTok=st.countTokens();
                for(int i=0;i<countTok;i++){
                    qu.add(st.nextToken());
                }
                m=br.readLine();
                if(m.trim().equals("#")){
                    break;
                }
            }
            String[]arr1=new String[qu.size()];
            for(int i=0;i<arr1.length;i++){
                arr1[i]=qu.remove();
            }
            Queue<String> qu2=new LinkedList<String>();
            while(true){
                StringTokenizer st=new StringTokenizer(m);
                int countTok=st.countTokens();
                for(int i=0;i<countTok;i++){
                    qu2.add(st.nextToken());
                }
                m=br.readLine();
                if(m.trim().equals("#")){
                    break;
                }
            }
            String[]arr2=new String[qu2.size()];
            for(int i=0;i<arr2.length;i++){
                arr2[i]=qu2.remove();
            }
            LinkedList<String> list=LCS(arr1, arr2);
            boolean first=true;
            while(!list.isEmpty()){
                if(!first)
                    sb.append(" ");
                sb.append(list.remove());
                first=false;
            }
            sb.append("\n");
        }
        System.out.print(sb);
    }
  
    static LinkedList<String> LCS(String[] m, String[] n) {
        int[][] arr = new int[m.length + 1][n.length + 1];
        for (int i = 0; i < m.length + 1; i++) {
            arr[i][0] = 0;
        }
        for (int i = 0; i < n.length + 1; i++) {
            arr[0][i] = 0;
        }
        for (int i = 0; i < m.length; i++) {
            for (int j = 0; j < n.length; j++) {
                if (m[i].equals(n[j])) {
                    arr[i + 1][j + 1] = arr[i][j] + 1;
                }else{
                   arr[i+1][j+1]=Math.max(arr[i+1][j],arr[i][j+1]);
                }
            }
        }
        int mpos = m.length, npos = n.length;
        LinkedList<String> result = new LinkedList<String>();

        while (mpos != 0 && npos != 0) {
            if (m[mpos - 1].equals(n[npos - 1])) {
                result.add(m[mpos - 1]);
                mpos--;
                npos--;
            } else if (arr[mpos][npos - 1] >= arr[mpos][npos]) {
                npos--;
            } else {
                mpos--;
            }
        }
        Collections.reverse(result);
        return result;
    }

}