Cod sursa(job #1799006)

Utilizator msciSergiu Marin msci Data 5 noiembrie 2016 17:34:52
Problema Cel mai lung subsir comun Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 2.61 kb
//package sergiu.algorithms;

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

public class LCS {
    FastScanner in;
    PrintWriter out;

    void solve() {
        int M = in.nextInt();
        int N = in.nextInt();
        int[] a = new int[M + 1];
        int[] b = new int[N + 1];
        for (int i = 1; i <= M; i++) a[i] = in.nextInt();
        for (int i = 1; i <= N; i++) b[i] = in.nextInt();

        int[][] dp = new int[M + 1][N + 1];

        for (int i = 0; i <= N; i++) dp[0][i] = 0;
        for (int i = 0; i <= M; i++) dp[i][0] = 0;

        ArrayList<Integer> fn = new ArrayList<>();

        for (int i = 1; i <= M; i++) {
            for (int j = 1; j <= N; j++) {
                if (a[i] == b[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    fn.add(a[i]);
                }
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        for (Integer i : fn) {
            out.print(i + " ");
        }
        out.println();
    }

    void run() {
        try {
            in = new FastScanner(new File("cmlsc.in"));
            out = new PrintWriter(new File("cmlsc.out"));

            solve();

            out.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    void runIO() {
        in = new FastScanner(System.in);
        out = new PrintWriter(System.out);

        solve();

        out.close();
    }

    class FastScanner {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public FastScanner(File f) {
            try {
                reader = new BufferedReader(new FileReader(f));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        public FastScanner(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
    }

    public static void main(String[] args) {
        new LCS().runIO();
    }
}