YChalk

Common Child

May 23rd, 2022 (edited)
489
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.*;
  2. import java.math.*;
  3. import java.security.*;
  4. import java.text.*;
  5. import java.util.*;
  6. import java.util.concurrent.*;
  7. import java.util.function.*;
  8. import java.util.regex.*;
  9. import java.util.stream.*;
  10. import static java.util.stream.Collectors.joining;
  11. import static java.util.stream.Collectors.toList;
  12.  
  13. class Result {
  14.  
  15.     /*
  16.      * Complete the 'commonChild' function below.
  17.      *
  18.      * The function is expected to return an INTEGER.
  19.      * The function accepts following parameters:
  20.      *  1. STRING s1
  21.      *  2. STRING s2
  22.      */
  23.  
  24.     public static int commonChild(String s1, String s2) {
  25.     // Write your code here
  26.         int result = 0;
  27.        
  28.         for (int i = 0; i < s1.length(); i++) {
  29.             int first = maxChild(s1, s2, i, 0);
  30.             int second = maxChild(s2, s1, i, 0);
  31.            
  32.             if (first > result) {
  33.                 result = first;
  34.             }  
  35.             if (second > result) {
  36.                 result = second;
  37.             }
  38.         }        
  39.        
  40.        
  41.         return result;
  42.     }
  43.    
  44.     public static int maxChild(String s1, String s2, int i1, int i2) {
  45.         if (i1 >= s1.length() || i2 >= s2.length()) {
  46.             return 0;
  47.         }
  48.        
  49.         char c1 = s1.charAt(i1);
  50.         int found = s2.indexOf(c1, i2);
  51.        
  52.         if (found == -1) {
  53.             return 0;
  54.         }
  55.        
  56.         int maxChild = 0;
  57.         int subsequent;        
  58.        
  59.         for (int i = i1+1; i < s1.length(); i++) {
  60.             subsequent = maxChild(s1, s2, i, found + 1);
  61.             if (subsequent > maxChild) {
  62.                 maxChild = subsequent;
  63.             }
  64.             //System.out.println(subsequent + " " + c1);
  65.         }
  66.        
  67.        
  68.         return maxChild + 1;
  69.     }  
  70.    
  71.  
  72. }
  73.  
  74. public class Solution {
  75.     public static void main(String[] args) throws IOException {
  76.         BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
  77.         BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
  78.  
  79.         String s1 = bufferedReader.readLine();
  80.  
  81.         String s2 = bufferedReader.readLine();
  82.  
  83.         int result = Result.commonChild(s1, s2);
  84.  
  85.         bufferedWriter.write(String.valueOf(result));
  86.         bufferedWriter.newLine();
  87.  
  88.         bufferedReader.close();
  89.         bufferedWriter.close();
  90.     }
  91. }
  92.  
RAW Paste Data Copied