import java.util.*;
import java.io.*;

public class TextMatcher2 {
    
    private static final boolean DEBUG = false;
    
    // DONE
    public static void main(String[] args) {

	if(args.length != 1) {
	    System.out.println("Usage: java Matcher <filename>");
	    System.out.println("File format:");
	    System.out.println("  Line 1 - \"tr\" string");
	    System.out.println("  Line 2 - \"ref\" string");
	    System.exit(0);
	}
	
	// Read and parse the file
	String[] input = parseFile(args[0]);
	StringTokenizer tokenized_tr = new StringTokenizer( input[0], " " );
	StringTokenizer tokenized_ref = new StringTokenizer( input[1], " " );
	
	// build TextAbstraction;
	TextAbstraction ta = new TextAbstraction();
	
	int[] tr;
	int[] ref;
	
	{ //block
	    ArrayList tr_arr = new ArrayList();
	    for(int i=0; tokenized_tr.hasMoreTokens(); i++) {
		String thisToken = tokenized_tr.nextToken();
		tr_arr.add(thisToken);
		ta.addWord(thisToken);
	    }
	    ArrayList ref_arr = new ArrayList();
	    for(int i=0; tokenized_ref.hasMoreTokens(); i++) {
		String thisToken = tokenized_ref.nextToken();
		ref_arr.add(thisToken);
		ta.addWord(thisToken);
	    }
	    
	    ta.lock(); // finished adding to ta
	    
	    // build tr
	    int size_tr = tr_arr.size();
	    tr = new int[size_tr];
	    for(int i=0; i < size_tr; i++) {
		tr[i] = ta.word2int((String)tr_arr.get(i)); 
	    }
	    
	    // build ref
	    int size_ref = ref_arr.size();
	    ref = new int[size_ref];
	    for(int i=0; i < size_ref; i++) {
		ref[i] = ta.word2int((String)ref_arr.get(i));
	    }
	} //end block
	
	// get matchings and find the best one
	ArrayList matches = match( tr, ref, ta );
	int bestscore = 2147483647; // max int value
	int bestpos = 0;
	for(int i=0; i < matches.size(); i++) {
	    int[] thismatch = (int[])matches.get(i);
	    int thisscore = getScore(thismatch);
	    if( thisscore < bestscore ) {
		bestscore = thisscore;
		bestpos = i;
	    }
	}
	
	// output results
	if(matches.size() > 0) {
	    int[] bestmatch = (int[])matches.get(bestpos);
	    // output number of matching words
	    System.out.println( bestmatch.length );
	    // output best alignment
	    System.out.println( bestscore );
	    // output the best sentence
	    System.out.print( ta.int2word( bestmatch[0] ) );
	    for(int i=0; i < bestmatch.length; i++) {
		System.out.print( " " + ta.int2word( bestmatch[i] ) );
	    }
	    System.out.print("\n");
	}
	else {
	    // no alignments
	    System.out.println("0");
	}
    }
    
    // DONE, I hope
    public static ArrayList match(int[] tr, int[] ref, TextAbstraction ta) {
	ArrayList ret = new ArrayList(); // the return value
	
	// Build relevant tr lists
	int[] sorted_tr = (int[])tr.clone();
	Arrays.sort( sorted_tr );
	//	int[] tr_indices = new int[tr.length];
	//	for(int i=0; i < tr_indices.length; i++) tr_indices[i] = i;
	
	// Build relevant ref lists
	int[] sorted_ref = (int[])ref.clone();
	Arrays.sort( sorted_ref );
	//	int[] ref_indices = new int[ref.length];
	//	for(int i=0; i < ref_indices.length; i++) ref_indices[i] = i;
	
	// Find common set with comparison (and build word count arrays)
	boolean[] common = new boolean[ta.size()]; // a hashmap really, and not strictly necessary since the wordcounts hold this information as well
	int[] wordcount_tr = new int[ta.size()];
	int[] wordcount_ref = new int[ta.size()];
	int tr_pos = 0;
	int ref_pos = 0;
	boolean foundACommonWord = false;
	while( tr_pos != sorted_tr.length && ref_pos != sorted_ref.length ) {
	    int t = sorted_tr[tr_pos];
	    int r = sorted_ref[ref_pos];
	    if( t < r ) {
		if( common[t] ) { wordcount_tr[t] = wordcount_tr[t]+1; }
		tr_pos++;
	    }
	    else if( t == r ) {
		foundACommonWord = true;
		common[t] = true;
		wordcount_tr[t] = wordcount_tr[t]+1;
		wordcount_ref[t] = wordcount_ref[t]+1;
		tr_pos++;
		ref_pos++;
	    }
	    else { // if( sorted_tr[tr_pos] > sorted_ref[ref_pos] ) {
		if( common[r] ) { wordcount_ref[r] = wordcount_ref[r]+1; }
		ref_pos++;
	    }
	}

	// If none in common, return here
	if( !foundACommonWord ) {
	    return ret;
	}
	
	// reduce tr
	int[] reduced_tr;
	{
	    int[] temp = new int[tr.length];
	    int pos = 0;
	    for(int i=0; i < tr.length; i++) {
		if( common[ tr[i] ] ) {
		    temp[pos] = tr[i];
		    pos++;
		}
	    }
	    reduced_tr = new int[pos];
	    for(int i=0; i < pos; i++) {
		reduced_tr[i] = temp[i];
	    }
	}

	// reduce ref
	int[] reduced_ref;
	{
	    int[] temp = new int[ref.length];
	    int pos = 0;
	    for(int i=0; i < ref.length; i++) {
		if( common[ ref[i] ] ) {
		    temp[pos] = ref[i];
		    pos++;
		}
	    }
	    reduced_ref = new int[pos];
	    for(int i=0; i < pos; i++) {
		reduced_ref[i] = temp[i];
	    }
	}

	// ******************************************************
	if(DEBUG) {
	    System.out.println("Common words, count_tr, count_ref:");
	    for(int i=0; i < common.length; i++) {
		if( common[i] ) System.out.print(" (" + i + "," + wordcount_tr[i]+","+wordcount_ref[i]+")");
	    }
	    System.out.println();
	    
	    System.out.println("reduced_tr:");
	    for(int i=0; i < reduced_tr.length; i++) {
		System.out.print(" " + reduced_tr[i]);
	    }
	    System.out.println();
	    
	    System.out.println("reduced_ref:");
	    for(int i=0; i < reduced_ref.length; i++) {
		System.out.print(" " + reduced_ref[i]);
	    }
	    System.out.println();
	    
	}
	// ******************************************************
	
	// build all orderings for tr
	ArrayList tr_orderings = getOrderings( reduced_tr, common, wordcount_tr, wordcount_ref );

	// build all orderings for ref
 	ArrayList ref_orderings = getOrderings( reduced_ref, common, wordcount_ref, wordcount_tr );
	
	// GARBAGE COLLECT
	System.gc();
	
	// create matchings, decide indices for the tr lines
	// IF NEED BE, THIS CAN BE TIME-OPTIMIZED FURTHER
	for(int a=0; a < tr_orderings.size(); a++) {
	    for(int b=0; b < ref_orderings.size(); b++) {
		int[] thistr = (int[])((int[])tr_orderings.get(a)).clone();
		int[] thisref = (int[])((int[])ref_orderings.get(b)).clone();
		int[] tr_chosen_indices = new int[ thistr.length ];
		for(int i=0; i < thistr.length; i++) {
		    for(int j=0; j < thisref.length; j++) {
			if( thisref[j] == thistr[i] ) {
			    tr_chosen_indices[i] = j;
			    thisref[j] = -1; // "delete" this entry
			    break; // Important!
			}
		    }
		}
		
		ret.add( tr_chosen_indices );
	    }
	}
	
	// return Alignment arrays, already in 0 - size ordering
	return ret;
    }


    // getOrderings() returns an ArrayList of int[]s or something, where each of the int[]s is just a straight representation of a part of the reduced text, which will line up with one of the other kind (tr or ref)
    private static ArrayList getOrderings( int[] list, boolean[] common, int[] wordcount_this, int[] wordcount_other ) {

	// find number of common words and build a mapping
	int[] map = new int[common.length];
	// Arrays.fill(map, -1);
	int commonsize = 0;
	for(int i=0; i < common.length; i++) {
	    if(common[i]) {
		map[i] = commonsize;
		commonsize++;
	    }
	}
	
	//	System.out.println("** commonsize = " + commonsize);
	
	// build the wordplacement array, which holds the indices of each common word from "list"
	ArrayList[] wordplacement = new ArrayList[commonsize];
	for(int i=0; i < commonsize; i++) {
	    wordplacement[i] = new ArrayList();
	}
	for(int i=0; i < list.length; i++) {
	    int here = list[i];
	    wordplacement[ map[here] ].add( new Integer(i) );
	}
	
	// build wordposition array, which takes the wordplacements, and enumerates all combinations of the indices, given how many of each are to be chosen
	ArrayList[] wordpositions = new ArrayList[commonsize];
	int totalCount = 0; // this value (to be built up) represents how many words long the alignment will be
	for(int i=0; i < commonsize; i++) {
	    ArrayList thislist = wordplacement[i];
	    
	    // pick the smaller of the wordcounts
	    int unMapThis = ((Integer)thislist.get(0)).intValue();
	    int val = list[unMapThis];
	    int select = wordcount_this[ val ];
	    if( wordcount_other[ val ] < select ) { 
		select = wordcount_other[ val ];
	    }

	    totalCount += select;
	    
	    if(DEBUG) System.out.println(" Select = " + select);
	    
	    ArrayList filled_array = new ArrayList();
	    fill( new int[select], select, 0, thislist, filled_array );
	    wordpositions[i] = filled_array;
	}

	// ************************************************************
	if(DEBUG) {
	    System.out.println("**** WORDPOSITIONS ****");
	    for(int i=0; i< wordpositions.length; i++) {
		System.out.print("  ");
		ArrayList z = wordpositions[i];
		for(int j=0; j < z.size(); j++) {
		    int[] q = (int[])z.get(j);
		    System.out.print(" [");
		    for(int k=0; k < q.length; k++) {
			System.out.print(q[k]+" ");
		    }
		    System.out.print("] ");
		}
		System.out.println();
	    }
	    
	    System.out.println("TotalCount = "+totalCount);
	} // OK :/ ?
	// ************************************************************
	

	ArrayList ret = new ArrayList();
	build( new int[totalCount], 0, 0, wordpositions, ret );
	// sort here or not?? Or sort and then convert right now? <--
	// Reorder and convert values back to "words"
	for(int i=0; i < ret.size(); i++) {
	    int[] arr = (int[])ret.get(i);
	    Arrays.sort( arr );
	    for(int j=0; j < arr.length; j++) {
		int newVal = list[ arr[j] ];
		arr[j] = newVal;
	    }
	}
	
	return ret;
    }


    // DONE, I think
    private static void fill( int[] soFar, int left_to_fill, int pos, ArrayList fromList, ArrayList finalResult ) {
	if( left_to_fill == 0 ) {
	    finalResult.add( (int[])soFar.clone() );
	    return;
	}
	else if( left_to_fill > (fromList.size()-pos) ) { return; }
	else {
	    fill( soFar, left_to_fill, pos+1, fromList, finalResult );
	    int[] copy = (int[])soFar.clone();
	    //	    System.out.println("soFar.length = " +soFar.length + "  left_to_fill = " + left_to_fill);
	    copy[ soFar.length - left_to_fill ] =
		((Integer)fromList.get(pos)).intValue();
	    fill( copy, left_to_fill-1, pos+1, fromList, finalResult );
	}
    }

    
    // returns ArrayList of int[]s
    private static void build( int[] soFar, int pos, int insertIndex, ArrayList[] wordpositions, ArrayList finalResult ) {
	ArrayList groups = wordpositions[pos];
	for(int i=0; i < groups.size(); i++) {
	    int[] ints = (int[])groups.get(i);
	    int[] copy = (int[])soFar.clone();
	    int index = insertIndex;
	    for(int j=0; j < ints.length; j++) {

		//		System.out.println(" COPY.LENGTH = "+copy.length+"  insertIndex = "+insertIndex+"  pos="+pos+"  wordpositions.length=" + wordpositions.length);

		//		try {
		copy[index] = ints[j];
		//		} catch(Exception e) {
		//		    System.out.println(e);
		//		    System.out.print("Adding "+ints[j]+" to ");
		//		    for(int ass=0; ass < copy.length; ass++) {
		//			System.out.print(" "+copy[ass]);
		//		    }
		//		    System.out.println();
		//		}
		index++;
	    }
	    if( pos == wordpositions.length-1 ) {
		finalResult.add(copy);
		return;
	    }
	    else {
		build( copy, pos+1, index, wordpositions, finalResult  );
	    }
	}
    }

	    
    // DONE
    private static String[] parseFile(String filename) {
	String[] ret = new String[2];
	try {
	    FileInputStream fis = new FileInputStream(filename);
	    
	    // NOTE: IF Using a charset other than standard ASCII, 
	    // then enter it in the constructor on the following line
	    InputStreamReader isr = new InputStreamReader(fis);
	    
	    // Setup the input reader
	    BufferedReader in = new BufferedReader( isr );

	    // Read the file
	    ret[0] = in.readLine();
	    ret[1] = in.readLine();
	} catch(Exception e) {
	    System.out.println("Error in parseFile(): " + e);
	    System.exit(0);
	}
	return ret;
    }
    
    // DONE
    public static int getScore(int[] arr) {
	// The following includes "chunking"

	int[] sorted_arr = (int[])arr.clone();
	Arrays.sort(sorted_arr);
	
	// convert arr to values 0 - arr.length
	LinkedList smush = new LinkedList();
	for(int i=0; i < arr.length; i++) {
	    // the following was already done earlier! :)
	    //int num = arr[i];
	    //for(int j=0; j < sorted_arr.length; j++) {
	    //if( sorted_arr[j] == num ) {
	    //   smush.add(new Integer(j));
	    //    break;
	    //}
	    //}
	    smush.add(new Integer(arr[i]));
	}
	
	for(int i=0; i < smush.size()-1; i++) {
	    int here = ((Integer)smush.get(i)).intValue();
	    int next = ((Integer)smush.get(i+1)).intValue();
	    if( here == next-1 ) {
		smush.remove(i);
		i--;
	    }
	}
	
	int[] curr = new int[smush.size()];
	for(int i=0; i < smush.size(); i++) {
	    curr[i] = ((Integer)smush.get(i)).intValue();
	}

	// NOTE! THIS IS WITHOUT CHUNKING -->
	//	int[] curr = (int[])arr.clone();
	
	int score = 0;
	boolean changed = false;
	do {
	    changed = false;
	    for(int j=0; j < curr.length - 1; j++) {
		if( curr[j] > curr[j+1] ) {
		    int temp = curr[j];
		    curr[j] = curr[j+1];
		    curr[j+1] = temp;
		    score++;
		    changed = true;
		}
	    }
	} while(changed);

	return score;
    }
    
}