import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;

public class Main {

    public static void main(String[] args) throws FileNotFoundException {
        int input = 0;
        if (args.length == 0)
            input = 10;
        else input = Integer.parseInt(args[0]);

        String Direct = System.getProperty("user.dir");
        if (Direct.indexOf("src") == -1)
            Direct += "\\src";
        String files = Direct + "\\product.txt";
        Scanner file = new Scanner(new File(files));
        ArrayList<String> list = new ArrayList<>();
        while (file.hasNextLine()) {
            list.add(file.nextLine());
        }
        file.close();

        Scanner key = new Scanner(System.in);
        System.out.println("Product Search - Input your keyword (s):");
        String name = key.nextLine();
        String[] parts = name.split(" ");

        ArrayList<data> Keep = new ArrayList<>();
        for (int j = 0; j < list.size(); j++) {
            data Store = new data(list.get(j));
            ArrayList<Integer> Index = new ArrayList<Integer>();
            for (int k = 0; k < parts.length; k++) {
                if (findBoyerMoore(list.get(j).toUpperCase().toCharArray(), parts[k].toUpperCase().toCharArray()) != -1) {
                    Index.add(findBoyerMoore(list.get(j).toUpperCase().toCharArray(), parts[k].toUpperCase().toCharArray()));
                    if (k == 0) {
                        Store.firstindex = findBoyerMoore(list.get(j).toUpperCase().toCharArray(), parts[k].toUpperCase().toCharArray());
                        Store.count++;

                    }
                }
            }
            Integer min = Integer.MAX_VALUE;
            for (int l = 0; l < Index.size(); l++) {
                for (int m = l + 1; m < Index.size(); m++) {
                    if (Math.abs((Index.get(l) - Index.get(m))) < min) {
                        min = (Math.abs((Index.get(l) - Index.get(m))));
                    }
                }
                Store.mDistance = min;
            }

            Keep.add(Store);
           // System.out.println(Store);
        }
        List<data> S = RadixSort(Keep);
        for (int i = 0; i < S.size(); i++) {
            if(S.get(i).count!=0)
            System.out.println(S.get(i).name);
        }
    }

        public static class data {
            String name;

            int firstindex, mDistance, Index, count;

            public data(String name) {
                this.name = name;
                count = 0;
                firstindex = Integer.MAX_VALUE;
                mDistance = Integer.MAX_VALUE;
            }

            @Override
            public String toString() {
                return name + " " + count + " " + firstindex + " " + mDistance;
            }
        }

        public static List<data> RadixSort(ArrayList < data > rData)
        {
            Integer max_count = 0, max_position = 0, max_minDist = 0;
            for (int i = 0; i < rData.size(); i++) {
                if (rData.get(i).firstindex > max_count)
                    max_count = rData.get(i).firstindex;
                if (rData.get(i).count > max_position)
                    max_position = rData.get(i).count;
                if (rData.get(i).mDistance > max_minDist)
                    max_minDist = rData.get(i).mDistance;
            }
            int digit_count = 0, digit_position = 0, digit_dist = 0;
            while (max_count > 0) {
                max_count = max_count / 10;
                digit_count++;
            }
            while (max_position > 0) {
                max_position = max_position / 10;
                digit_position++;
            }
            while (max_minDist > 0) {
                max_minDist = max_minDist / 10;
                digit_dist++;
            }
            LinkedList<data> Bucket1 = new LinkedList<>();
            for (int i = 0; i < rData.size(); i++)
            {
                Bucket1.add(rData.get(i));
            }
            int d = 1;
            for (int i = 1; i <= digit_dist; i++) {
                LinkedList<data> tmp = new LinkedList<>();
                for (int j = 0; j < 10; j++) {
                    for (int k = 0; k < Bucket1.size(); k++) {
                        if ((Bucket1.get(k).mDistance / d) % 10 == j)
                            tmp.add(Bucket1.get(k));
                    }
                }
                Bucket1 = new LinkedList<>();
                for (int j = 0; j < tmp.size(); j++) {
                    Bucket1.add(tmp.get(j));
                }
                d *= 10;
            }
            d = 1;
            for (int i = 1; i <= digit_position; i++) {
                LinkedList<data> tmp = new LinkedList<>();
                for (int j = 0; j < 10; j++) {
                    for (int k = 0; k < Bucket1.size(); k++) {
                        if ((Bucket1.get(k).firstindex / d) % 10 == j)
                            tmp.add(Bucket1.get(k));
                    }
                }
                Bucket1 = new LinkedList<>();
                for (int j = 0; j < tmp.size(); j++) {
                    Bucket1.add(tmp.get(j));
                }
                d *= 10;
            }
            d = 1;
            for (int i = 1; i <= digit_count; i++) {
                LinkedList<data> tmp = new LinkedList<>();
                for (int j = 9; j >= 0; j--) {
                    for (int k = 0; k < Bucket1.size(); k++) {
                        if ((Bucket1.get(k).count / d) % 10 == j)
                            tmp.add(Bucket1.get(k));
                    }
                }
                Bucket1 = new LinkedList<>();
                for (int j = 0; j < tmp.size(); j++) {
                    Bucket1.add(tmp.get(j));
                }
                d *= 10;
            }
            return Bucket1;
        }

    public static int findBoyerMoore(char[] text, char[] pattern) {
        int n = text.length;
        int m = pattern.length;
        if (m == 0) return 0;
        Map<Character, Integer> last = new HashMap<>(); // the 'last' map
        for (int i = 0; i < n; i++)
            last.put(text[i], -1); // set −1 as default for all text characters
        for (int k = 0; k < m; k++) {
            last.put(pattern[k], k);
        }
        int i = m - 1;
        int k = m - 1;
        while (i < n) {
            if (text[i] == pattern[k]) { // a matching character
                if (k == 0) return i; // entire pattern has been found
                i--; // otherwise, examine previous
                k--; // characters of text/pattern
            } else {
                i += m - Math.min(k, 1 + last.get(text[i])); // case analysis for jump step
                k = m - 1;
                // restart at end of pattern
            }
        }
        return -1;
    }
}