Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //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)
- import java.io.*;
- import java.util.*;
- public class LexicographicallyLargestCommonSubsequence{
- static int[] alph = new int[26];
- static int[] start;
- static String ans = "";
- static String rev = "";
- public static String lcs(String[] strings, String lcs, int follow) {
- if(follow >= rev.length()) {
- if(lcs == "")return "-1";
- else return lcs;
- }
- char curchar = rev.charAt(follow);
- int n = strings.length;
- int loc[] = new int[n]; //where to start next string
- boolean flag = true;
- for(int i = 0; i < n; i++) { //iterate i through number of strings
- for(int j = start[i]; j < strings[i].length(); j++) { //iterate j through length of current string
- if(strings[i].charAt(j) == curchar) {
- loc[i] = j+1;
- break;
- }
- }
- if(loc[i] == 0) { // one of the strings does not have the letter
- flag = false;
- break;
- }
- }
- if(flag) {
- for(int i = 0; i < n; i++) {
- // strings[i] = strings[i].substring(loc[i]);
- start[i] = loc[i];
- }
- return lcs(strings, lcs+curchar, follow+1);
- }else {
- return lcs(strings, lcs, follow+1);
- }
- }
- public static String lcs2(String[] strings, String lcs, int curchar, int[] curpos) {
- int n = strings.length;
- int loc[] = new int[n]; //where to start next string
- Boolean flag = true;
- int nextchar = -1;
- for(int i = curchar; i >= 0; i--) {
- flag = true;
- for(int j = 0; j < n; j++) {
- if(!mp.get(j).containsKey(i)) {
- flag = false;
- break;
- }else {
- while(!mp.get(j).get(i).isEmpty() && mp.get(j).get(i).peek() <= curpos[j]) {
- // System.out.println(mp.get(j).get(i).peek()+" "+ curpos[j] + " "+(char)i);
- mp.get(j).get(i).poll();
- }
- // System.out.println("");
- if(mp.get(j).get(i).isEmpty()) {
- flag = false;
- break;
- }else {
- loc[j] = mp.get(j).get(i).peek();
- }
- }
- }
- if(flag) {
- nextchar = i;
- // System.out.println((char) nextchar);
- for(int j = 0; j < n; j++) {
- curpos[j]=loc[j];
- }
- break;
- }
- }
- // System.out.println(Arrays.toString(curpos));
- if(nextchar == -1) {
- if(lcs=="")return "-1";
- return lcs;
- }
- return lcs2(strings, lcs+(char)nextchar, (char)nextchar, curpos);
- }
- static String lcs = "";
- static HashMap<Integer, HashMap<Integer, Queue<Integer>>> mp = new HashMap<>();
- public static void main(String[] args) throws NumberFormatException, IOException {
- BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
- int n = Integer.parseInt(br.readLine());
- String[] strings = new String[n];
- for(int i = 0 ; i < n; i++) {
- strings[i] = br.readLine();
- }
- // long startTime = System.nanoTime();
- start = new int[n];
- // for(int i = 0; i < n; i++) {
- // mp.put(i, new HashMap<Integer, Queue<Integer>>());
- // for(int j = 0; j < strings[i].length(); j++) {
- // if(!mp.get(i).containsKey((int) strings[i].charAt(j)))
- // mp.get(i).put((int) strings[i].charAt(j), new LinkedList<Integer>());
- //
- // mp.get(i).get((int) strings[i].charAt(j)).add(j+1); //put the current char index into the current char
- // }
- // }
- // System.out.println(mp);
- rev = "";
- PriorityQueue<Integer> reverse = new PriorityQueue<>(Collections.reverseOrder());
- for(int i = 0; i < strings[0].length(); i++) {
- reverse.add((int)strings[0].charAt(i));
- }
- for(int i = 0; i < strings[0].length(); i++) {
- int tmp = reverse.poll();
- rev+=(char)tmp;
- }
- // System.out.println(rev);
- // System.out.println(lcs2(strings, "", (int)'z', new int[n]));
- System.out.println(lcs(strings, "", 0));
- // long endTime = System.nanoTime();
- // long totalTime = endTime - startTime;
- // System.out.println(totalTime);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement