fork(1) download
copy 
  1. import java.util.*;
  2.  
  3. public class Main {
  4.  
  5. 	public static void main(String[] args) {
  6. 		Scanner in = new Scanner(System.in);
  7. 		int tests = Integer.parseInt(in.nextLine());
  8.  
  9. 		for(int i = 0; i < tests; i++) {
  10. 			int max = 0;
  11.  
  12. 			String ag = in.nextLine();
  13. 			ag = ag.replaceAll("\\s","");
  14. 			String tom = in.nextLine();
  15. 			tom = tom.replaceAll("\\s","");
  16.  
  17. 			while (!tom.equals("0")) {
  18. 				int cross = LCS(ag,tom);
  19. 				max = Math.max(cross, max);
  20. 				System.out.println("ag: " + ag);
  21. 				System.out.println("tom: " + tom);
  22. 				System.out.println("cross: " + cross);
  23. 				tom = in.nextLine();
  24. 				tom = tom.replaceAll("\\s","");
  25. 			}
  26.  
  27. 			// Print the maximum common checkpoints.
  28. 			System.out.println(max - 1);
  29. 		}
  30.  
  31. 	}
  32.  
  33. 	private static int LCS(String x, String y) {
  34.         int M = x.length();
  35.         int N = y.length();
  36.  
  37.         // opt[i][j] = length of LCS of x[i..M] and y[j..N]
  38.         int[][] opt = new int[M+1][N+1];
  39.  
  40.         // compute length of LCS and all subproblems via dynamic programming
  41.         for (int i = M-1; i >= 0; i--) {
  42.             for (int j = N-1; j >= 0; j--) {
  43.                 if (x.charAt(i) == y.charAt(j))
  44.                     opt[i][j] = opt[i+1][j+1] + 1;
  45.                 else 
  46.                     opt[i][j] = Math.max(opt[i+1][j], opt[i][j+1]);
  47.             }
  48.         }
  49.  
  50. 		return opt[0][0];
  51. 	}
  52. }
  53.  
Success #stdin #stdout 0.09s 380672KB
comments (?)
stdin
copy 
2
1 2 3 4 5 6 7 8 9 0
1 1 1 1 1 1 2 3 0
1 3 1 3 5 7 8 9 3 4 0
0
1 2 3 0
3 0
0
stdout
copy 
ag: 1234567890
tom: 111111230
cross: 4
ag: 1234567890
tom: 13135789340
cross: 7
6
ag: 1230
tom: 30
cross: 2
1
https://ideone.com/40IE5G
language:
Java (12.0.1)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!