Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Pokatov Stepan
- //program for calculating greatest common subsequence
- //21.11.2018
- import java.util.Scanner;
- public class NOPodp {
- public static void main(String[] args) {
- Scanner sc = new Scanner(System.in);
- int N = sc.nextInt();
- int n[] = new int[N];
- for (int i = 0; i < N; i++) {
- n[i] = sc.nextInt();
- }
- int M = sc.nextInt();
- int m[] = new int[M];
- for (int i = 0; i < M; i++) {
- m[i] = sc.nextInt();
- }
- int A[][] = new int[N][M];
- int max=0, x=0, y=0;
- if (n[0] == m[0]) {
- A[0][0] = 1;
- }
- for (int i = 1; i < N; i++) {
- if ((n[i] == m[0]) || (A[i - 1][0] == 1)) {
- A[i][0] = 1;
- if (A[i][0]>max) {
- max=A[i][0];
- x=i;
- y=0;
- }
- }
- }
- for (int i = 1; i < M; i++) {
- if ((n[0] == m[i]) || (A[0][i - 1] == 1)) {
- A[0][i] = 1;
- if (A[0][i]>max) {
- max=A[0][i];
- x=0;
- y=i;
- }
- }
- }
- for (int i = 1; i < N; i++) {
- for (int j = 1; j < M; j++) {
- if (n[i] == m[j]) {
- A[i][j] = A[i - 1][j - 1] + 1;
- if (A[i][j]>max) {
- max=A[i][j];
- x=i;
- y=j;
- }
- } else {
- A[i][j] = 0;
- }
- }
- }
- System.out.println(A[x][y]);
- int help = A[x][y] - 1;
- int B[] = new int[A[x][y]];
- int i = y;
- int j = x;
- while (help > -1) {
- if (n[j] == m[i]) {
- B[help] = m[i];
- i--;
- j--;
- help--;
- }
- }
- for (int l = 0; l < A[x][y]; l++) {
- System.out.print(B[l] + " ");
- }
- sc.close();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement