fork download
copy 
  1. /**
  2.  * Longest Common Sequence
  3.  * @author Prateek Rathore
  4.  */
  5.  class LCS {
  6.  
  7. 	/**
  8. 	 * Longest Common Sequnece Subroutine
  9. 	 */
  10. 	public static int lcs(String s1, String s2){
  11.  
  12. 		char[] X = s1.toCharArray();
  13. 		char[] Y = s2.toCharArray();
  14. 		int[][] LCS = new int[Y.length +1 ][X.length +1 ];
  15.  
  16. 		for(int i=1;i<=Y.length;i++)
  17. 		{
  18. 			for(int j=1;j<=X.length;j++)
  19. 			{
  20. 				if(Y[i -1 ]== X[j-1])
  21. 					LCS[i][j] = 1 + LCS[i-1][j-1];
  22. 				else
  23. 					LCS[i][j] = Math.max(LCS[i-1][j], LCS[i][j-1]);
  24. 			}
  25. 		}
  26.  
  27. 		// Start Trace Back
  28. 		StringBuilder sb= new StringBuilder();
  29. 		int i=Y.length ;
  30. 		int j=X.length ;
  31.  
  32. 		while(i > 0 && j>0)
  33. 		{
  34. 			//System.out.println(i + " " + j);
  35. 			if(Y[i-1] == X[j-1])
  36. 			{
  37. 				sb = sb.append(X[j-1]);
  38. 				i--;
  39. 				j--;
  40. 			}
  41. 			else
  42. 			{
  43. 				if(LCS[i][j-1]> LCS[i-1][j])  
  44. 					j--;
  45. 				else
  46. 					i--;
  47. 			}
  48. 		}
  49.  
  50. 		System.out.println(sb.reverse());
  51. 		return LCS[Y.length][X.length];
  52. 	}
  53.  
  54. 	public static void main(String[] args) {
  55. 		/*String s1= "ADBAVCEB";
  56. 		String s2= "ABACEB";*/
  57.  
  58. 		String s1= "PRATEEK";
  59. 		String s2= "RATHORE";
  60.  
  61. 		/*String s1= "DYNAMIC";
  62. 		String s2= "PROGRAMMING";*/
  63.  
  64. 		/*String s1= "DILTOPAGALHAI";
  65. 		String s2= "PAGALPANTIHAI";*/
  66.  
  67. 		System.out.println(lcs(s1.toUpperCase(),s2.toUpperCase()));
  68. 	}
  69. }
  70.  
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
RATE
4
https://ideone.com/eWMS0Z
language:
Java (12.0.1)
created:
10 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!