fork(4) download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	public static void main (String[] args) throws java.lang.Exception
  11. 	{
  12. 		 char[] s1= "ABCDGH".toCharArray();
  13.       char[] s2="AEDFHR".toCharArray();
  14.       System.out.println("\ns1 = "+Arrays.toString(s1));
  15.      System.out.println("s2 = "+Arrays.toString(s2));
  16.  
  17.  
  18.       String ans="";
  19.      int lcs_length=naive(s1,s2,s1.length,s2.length,ans);
  20.  
  21.  
  22.          System.out.println("LCS length(Using Recursion) = "+lcs_length);
  23.  
  24.     LCS_DP(s1,s2);
  25. 	}
  26. 	public static int naive(char[] s1,char[] s2,int l1,int l2,String s)
  27.     {
  28.  
  29.         if(l1==0 || l2==0)
  30.         {
  31.             return 0;
  32.         }
  33.  
  34.         if(s1[l1-1]==s2[l2-1])
  35.         {
  36.        //   System.out.println(l1+" "+l2+" "+s1[l1]+ " check 2");
  37.             s=s1[l1-1]+s;
  38.             return naive(s1,s2,l1-1,l2-1,s)+1;
  39.         }
  40.         else
  41.         {
  42.             int f1=naive(s1, s2, l1, l2-1,s);
  43.             int f2=naive(s1, s2, l1-1, l2,s);
  44.             return Math.max(f1, f2);
  45.         }
  46.     }
  47.  
  48.     public static void LCS_DP(char[] s1,char[] s2)
  49.     {
  50.         if(s1.length==0 || s2.length==0)
  51.             return ;
  52.  
  53.         int l1=s1.length,l2=s2.length;
  54.  
  55.         int m[][]=new int[l1+1][l2+1];
  56.  
  57.         int i,j;
  58.  
  59.         System.out.print("LCS String = ");
  60.        for(i=0;i<=l1;i++)
  61.         {
  62.             for(j=0;j<=l2;j++)
  63.             {
  64.                 if(i==0 || j==0)
  65.                 {
  66.                     m[i][j]=0;
  67.                 }
  68.  
  69.                 else
  70.                 {
  71.                     if(s1[i-1]==s2[j-1] )
  72.                     {
  73.                         m[i][j]=m[i-1][j-1]+1;
  74.                         System.out.print(s1[i-1]);
  75.                     }
  76.                     else
  77.                     {
  78.                        m[i][j]=Math.max(m[i][j-1],m[i-1][j]);
  79.                     }
  80.  
  81.                 }
  82.             }
  83.         }
  84.  
  85.         System.out.println("\nLength (Using DP) = "+m[l1][l2]);
  86.     }
  87. }
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
s1 = [A, B, C, D, G, H]
s2 = [A, E, D, F, H, R]
LCS length(Using Recursion) = 3
LCS String = ADH
Length (Using DP) = 3
https://ideone.com/fsgBNB
language:
Java (HotSpot 12)
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!