SHARE
TWEET

vêaí

a guest Jun 19th, 2019 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2. public class al8b {
  3.  
  4.     public static void main(String[] args) {
  5.         Scanner in = new Scanner(System.in);
  6.         while(in.hasNext()) {
  7.             String str1 = in.nextLine();
  8.             String str2 = in.nextLine();
  9.             int tam1 = str1.length();
  10.             int tam2 = str2.length();
  11.             String nstr;
  12.             int cont = 0;
  13.             System.out.println(lcs(str1, tam1, str2, tam2, cont));
  14.             /*for(int i = str1.length() - 1; i >= 0; i--) {
  15.                 char c = str1.charAt(i);
  16.                 String n = "" + c;
  17.                 for(int j = tam2 - 1; j >= 0; j--) {
  18.                     if(str2.charAt(j) == c) {
  19.                         str2 = str2.replaceFirst(n, "");
  20.                         cont++;
  21.                         tam2--;
  22.                         j = -1;
  23.                     } else if(j == 0) {
  24.                         str2 = str2.substring(0, tam2 - 1);
  25.                         tam2--;
  26.                     }
  27.                 }
  28.             }*/
  29.  
  30.             //System.out.println(cont);
  31.         }
  32.     }
  33.  
  34.     public static int lcs(String str1, int tam1, String str2, int tam2, int res) {
  35.         if(tam1 == 0 || tam2 == 0) {
  36.             return res;
  37.         } else if(str1.charAt(tam1 - 1) == str2.charAt(tam2 - 1)) {
  38.             str1 = str1.substring(0, tam1 - 1);
  39.             str2 = str2.substring(0, tam2 - 1);
  40.             tam1--;
  41.             tam2--;
  42.             res = res + 1 + lcs(str1, tam1, str2, tam2, res);
  43.         } else {
  44.             if(lcs(str1.substring(0, tam1 - 1), tam1 - 1, str2, tam2, res) > lcs(str1, tam1, str2.substring(0, tam2 - 1), tam2 - 1, res)) {
  45.                 res = res + lcs(str1.substring(0, tam1 - 1), tam1 - 1, str2, tam2, res);
  46.             } else {
  47.                 res = res + lcs(str1, tam1, str2.substring(0, tam2 - 1), tam2 - 1, res);
  48.             }
  49.         }
  50.         return res;
  51.     }
  52.  
  53. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top