String Finding

QUESTION

You are given n strings w1, w2, ……, wn. Let Si denote the set of strings formed by considering all unique substrings of the string wi. A substring is defined as a contiguous sequence of one or more characters in the string. More information on substrings can be found here. Let S = {S1 U S2 U …. Sn} .i.e S is a set of strings formed by considering all the unique strings in all sets S1, S2, ….. Sn. You will be given many queries, and for each query, you will be given an integer ‘k’. Your task is to display the lexicographically kth smallest string from the set S.\n\nInput Format\n\nThe first line of input contains a single integer n, denoting the number of strings. Each of the next n lines consists of a string. The string on the ith line (1<=i<=n) is denoted by wi and has a length mi. The next line consists of a single integer q, denoting the number of queries. Each of the next q lines consists of a single integer k.\n\nNote: The input strings consist only of lowercase english alphabets ‘a’ – ‘z’.\n\nConstraints\n\n1<= n <=50 \n1<= mi <=2000 \n1<= q <=500 \n1<= k <=1000000000\n\nOutput Format\n\nOutput q lines, where the ith line consists of a string which is the answer to the ith query. If the input is invalid (i.e., k > size of S), display \”INVALID\” for that case.

ANSWER

import java.util.ArrayList;
    import java.util.Scanner;
    import java.util.TreeSet;
    
    public class TestClass {
    
        private static final String INVALID = "INVALID";
        private TreeSet<String> mainset = new TreeSet<String>();
        private ArrayList<String> array = new ArrayList<String>();
        private String[] main_ary;
        private int length;
        
        public static void main(String args[]) {
            long start=System.currentTimeMillis();
            TestClass fin = new TestClass();
          //  System.out.println(System.currentTimeMillis()-start);
            Scanner scanner = new Scanner(System.in);
            int num_of_strings = scanner.nextInt();
            long pr=System.currentTimeMillis();
            
            for (int i = num_of_strings; --i >=0;) {
                fin.process(scanner.next());
            }
         //   System.out.println("pr took "+(System.currentTimeMillis()-pr));
            long in=System.currentTimeMillis();
            
            fin.initialize();
        //    System.out.println("in took "+(System.currentTimeMillis()-in));
            
            
            int num_of_queries = scanner.nextInt();
            int length=fin.length;
            long qu=System.currentTimeMillis();
            for (int i = num_of_queries; --i >=0;) {
                int index=scanner.nextInt()-1;
                if(index<length)
                {
                    System.out.println(fin.query(index));
                }
                else
                {
                    System.out.println(INVALID);
                }
            }
       //     System.out.println("qu took "+(System.currentTimeMillis()-qu));
        }
    
        private String query(int index) {
                return main_ary[index];
               // return array.get(index);
        }
    
        private void process(String input) {
            int len = input.length();
            for (int i = 0; i < len; i++) {
                for (int j = i; j < len; j++) {
                    mainset.add(input.substring(i, j + 1));
                }
            }
        }
    
        private void initialize() {
          length=mainset.size();
            main_ary=(String[]) mainset.toArray(new String[length]);
        //    array.addAll(mainset);
            
        }
    }
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro