Advertisement
Guest User

Untitled

a guest
Nov 15th, 2019
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.99 KB | None | 0 0
  1. //lcs2 is not used and lcs just follows the reverse of the first string (maybe change it to just the backwards alphabet and change when each letter is incremented)
  2.  
  3. import java.io.*;
  4. import java.util.*;
  5.  
  6. public class LexicographicallyLargestCommonSubsequence{
  7.     static int[] alph = new int[26];
  8.     static int[] start;
  9.     static String ans = "";
  10.     static String rev = "";
  11.     public static String lcs(String[] strings, String lcs, int follow) {
  12.         if(follow >= rev.length()) {                       
  13.             if(lcs == "")return "-1";
  14.             else return lcs;
  15.         }
  16.         char curchar = rev.charAt(follow);
  17.        
  18.         int n = strings.length;
  19.         int loc[] = new int[n];                                         //where to start next string
  20.         boolean flag = true;
  21.  
  22.         for(int i = 0; i < n; i++) {                                    //iterate i through number of strings
  23.             for(int j = start[i]; j < strings[i].length(); j++) {           //iterate j through length of current string
  24.                 if(strings[i].charAt(j) == curchar) {
  25.                     loc[i] = j+1;
  26.                     break;
  27.                 }
  28.             }  
  29.             if(loc[i] == 0) {                                           // one of the strings does not have the letter
  30.                 flag = false;
  31.                 break;
  32.             }
  33.         }
  34.  
  35.         if(flag) {
  36.             for(int i = 0; i < n; i++) {
  37. //              strings[i] = strings[i].substring(loc[i]);
  38.                 start[i] = loc[i];
  39.             }
  40.             return lcs(strings, lcs+curchar,  follow+1);
  41.         }else {
  42.             return lcs(strings, lcs, follow+1);
  43.         }
  44.        
  45.        
  46.     }
  47.    
  48.     public static String lcs2(String[] strings, String lcs, int curchar, int[] curpos) {
  49.  
  50.         int n = strings.length;
  51.        
  52.         int loc[] = new int[n];                             //where to start next string
  53.        
  54.         Boolean flag = true;
  55.         int nextchar = -1;
  56.        
  57.         for(int i = curchar; i >= 0; i--) {
  58.             flag = true;
  59.             for(int j = 0; j < n; j++) {
  60.  
  61.                
  62.                 if(!mp.get(j).containsKey(i)) {
  63.                     flag = false;
  64.                     break;
  65.                 }else {
  66.                     while(!mp.get(j).get(i).isEmpty() && mp.get(j).get(i).peek() <= curpos[j]) {
  67. //                      System.out.println(mp.get(j).get(i).peek()+"  "+ curpos[j] + " "+(char)i);
  68.                         mp.get(j).get(i).poll();
  69.                     }
  70. //                  System.out.println("");
  71.                     if(mp.get(j).get(i).isEmpty()) {
  72.                         flag = false;
  73.                         break;
  74.                     }else {
  75.                         loc[j] = mp.get(j).get(i).peek();
  76.  
  77.                     }
  78.                 }
  79.             }
  80.            
  81.             if(flag) {
  82.                 nextchar = i;
  83. //              System.out.println((char) nextchar);
  84.                
  85.                 for(int j = 0; j < n; j++) {
  86.                     curpos[j]=loc[j];
  87.                 }
  88.                 break;
  89.             }
  90.            
  91.         }
  92.        
  93. //      System.out.println(Arrays.toString(curpos));
  94.         if(nextchar == -1) {
  95.             if(lcs=="")return "-1";
  96.             return lcs;
  97.         }
  98.        
  99.        
  100.         return lcs2(strings, lcs+(char)nextchar, (char)nextchar, curpos);
  101.        
  102.        
  103.        
  104.     }
  105.     static String lcs = "";
  106.    
  107.     static HashMap<Integer, HashMap<Integer, Queue<Integer>>> mp = new HashMap<>();
  108.    
  109.     public static void main(String[] args) throws NumberFormatException, IOException {
  110.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  111.         int n = Integer.parseInt(br.readLine());
  112.         String[] strings = new String[n];
  113.         for(int i = 0 ; i < n; i++) {
  114.             strings[i] = br.readLine();
  115.         }
  116. //      long startTime = System.nanoTime();
  117.        
  118.         start = new int[n];
  119.  
  120. //      for(int i = 0; i < n; i++) {
  121. //          mp.put(i,  new HashMap<Integer, Queue<Integer>>());
  122. //          for(int j = 0; j < strings[i].length(); j++) {
  123. //              if(!mp.get(i).containsKey((int) strings[i].charAt(j)))
  124. //                  mp.get(i).put((int) strings[i].charAt(j), new LinkedList<Integer>());
  125. //             
  126. //              mp.get(i).get((int) strings[i].charAt(j)).add(j+1);                              //put the current char index into the current char
  127. //          }
  128. //      }
  129. //      System.out.println(mp);
  130.         rev = "";
  131.         PriorityQueue<Integer> reverse = new PriorityQueue<>(Collections.reverseOrder());
  132.        
  133.         for(int i = 0; i < strings[0].length(); i++) {
  134.             reverse.add((int)strings[0].charAt(i));
  135.         }
  136.         for(int i = 0; i < strings[0].length(); i++) {
  137.             int tmp = reverse.poll();
  138.             rev+=(char)tmp;
  139.         }
  140. //      System.out.println(rev);
  141. //      System.out.println(lcs2(strings, "", (int)'z', new int[n]));
  142.         System.out.println(lcs(strings, "", 0));
  143.        
  144. //      long endTime   = System.nanoTime();
  145. //      long totalTime = endTime - startTime;
  146. //      System.out.println(totalTime);
  147.     }
  148. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement