Advertisement
Guest User

Untitled

a guest
Nov 21st, 2018
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.50 KB | None | 0 0
  1. //Pokatov Stepan
  2. //program for calculating greatest common subsequence
  3. //21.11.2018
  4. import java.util.Scanner;
  5.  
  6. public class NOPodp {
  7.  
  8. public static void main(String[] args) {
  9. Scanner sc = new Scanner(System.in);
  10. int N = sc.nextInt();
  11. int n[] = new int[N];
  12. for (int i = 0; i < N; i++) {
  13. n[i] = sc.nextInt();
  14. }
  15. int M = sc.nextInt();
  16. int m[] = new int[M];
  17. for (int i = 0; i < M; i++) {
  18. m[i] = sc.nextInt();
  19. }
  20. int A[][] = new int[N][M];
  21. int max=0, x=0, y=0;
  22.  
  23. if (n[0] == m[0]) {
  24. A[0][0] = 1;
  25. }
  26.  
  27. for (int i = 1; i < N; i++) {
  28. if ((n[i] == m[0]) || (A[i - 1][0] == 1)) {
  29. A[i][0] = 1;
  30. if (A[i][0]>max) {
  31. max=A[i][0];
  32. x=i;
  33. y=0;
  34. }
  35. }
  36. }
  37.  
  38. for (int i = 1; i < M; i++) {
  39. if ((n[0] == m[i]) || (A[0][i - 1] == 1)) {
  40. A[0][i] = 1;
  41. if (A[0][i]>max) {
  42. max=A[0][i];
  43. x=0;
  44. y=i;
  45. }
  46. }
  47. }
  48.  
  49. for (int i = 1; i < N; i++) {
  50. for (int j = 1; j < M; j++) {
  51. if (n[i] == m[j]) {
  52. A[i][j] = A[i - 1][j - 1] + 1;
  53. if (A[i][j]>max) {
  54. max=A[i][j];
  55. x=i;
  56. y=j;
  57. }
  58. } else {
  59. A[i][j] = 0;
  60. }
  61. }
  62. }
  63.  
  64. System.out.println(A[x][y]);
  65. int help = A[x][y] - 1;
  66. int B[] = new int[A[x][y]];
  67. int i = y;
  68. int j = x;
  69.  
  70. while (help > -1) {
  71. if (n[j] == m[i]) {
  72. B[help] = m[i];
  73. i--;
  74. j--;
  75. help--;
  76. }
  77. }
  78.  
  79. for (int l = 0; l < A[x][y]; l++) {
  80. System.out.print(B[l] + " ");
  81. }
  82.  
  83. sc.close();
  84. }
  85. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement