Sunday, December 2, 2012

CodeEval Longest Common Subsequence

// CodeEval Longest Common Subsequence

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

class Main {
    public static void main(String[] args) {
        lcs.main(args);
    }
}

class lcs {
    public static void main(String[] args) {
        boolean LOCAL_TEST = false;
        // LOCAL_TEST = true;// comment it before submitting
        if (LOCAL_TEST)
            CodeEvalGetInput("e:\\zin.txt");
        else
            CodeEvalGetInput(args[0]);
    }

    public static void CodeEvalGetInput(String arg) {
        try {
            File file = new File(arg);
            BufferedReader in = new BufferedReader(new FileReader(file));
            Initialize();
            String line;
            while ((line = in.readLine()) != null) {
                if (line.trim().equals(""))
                    continue;
                String[] lineArray = line.split(";");
                if (lineArray.length > 0) {
                    // Process line of input Here
                    Process(lineArray);
                }
            }
        } catch (IOException e) {
            System.out.println("File Read Error: " + e.getMessage());
        }
    }

    private static void Initialize() {
    }

    private static void Process(String[] lineArray) {
        String S1 = lineArray[0].trim();
        String S2 = lineArray[1].trim();
        String lcs = LCSAsString(S1, S2);
        System.out.println(lcs.trim());
    }

    public static String LCSAsString(String X, String Y) {
        int M = X.length();
        int N = Y.length();
        int[][] lcs = new int[M + 1][N + 1];
        String[][] lcsString = new String[M + 1][N + 1];
        for (int i = 0; i <= M; i++) {
            lcs[i][0] = 0;
            lcsString[i][0] = "";
        }
        for (int j = 0; j <= N; j++) {
            lcs[0][j] = 0;
            lcsString[0][j] = "";
        }
        for (int i = 1; i <= M; i++)
            for (int j = 1; j <= N; j++) {
                if (X.charAt(i - 1) == Y.charAt(j - 1)) {
                    lcs[i][j] = lcs[i - 1][j - 1] + 1;
                    lcsString[i][j] = lcsString[i - 1][j - 1]
                            + String.valueOf(X.charAt(i - 1));
                } else {
                    lcs[i][j] = Math.max(lcs[i - 1][j], lcs[i][j - 1]);
                    if (lcs[i - 1][j] > lcs[i][j - 1])
                        lcsString[i][j] = lcsString[i - 1][j];
                    else
                        lcsString[i][j] = lcsString[i][j - 1];
                }
            }
        return lcsString[M][N];
    }

}

No comments:

Post a Comment