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

public class Main {

    public static void main(String[] args) throws FileNotFoundException {

            int input = 0,input2 = 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";


            Scanner file = new Scanner(new File("C:\\Users\\GL\\Desktop\\Algor\\HomeWork2\\product.txt"));
            ArrayList<String> list = new ArrayList<>();
            while (file.hasNextLine()) {
                list.add(file.nextLine());
            }
            file.close();



            Scanner key = new Scanner(System.in);
            System.out.print("Product Search - Input your keyword (s): ");
            String name = key.nextLine();

            String[] seg = name.split(" ");
        while(name.length() > 0)
        {

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

            }
            int note = 0;
            List<Database> S = RadixSort(Keep);
            int z=0;
            while (z<S.size())
            {
                if (S.get(z).firstindex > 1000)
                {
                    z=0;

                    break;
                }
                note = z;
                z++;
            } note++;

            if(note > input)
            {
                note = input;
            }
            if (note ==  1)
            {
                note=0;


            }

            for (int i = 0; i < note ; i++) {
                    System.out.println(S.get(i).name);
            }
            System.out.println(note + " product(s) matched");
            System.out.println();
             key = new Scanner(System.in);

            System.out.print("Product Search - Input your keyword (s): ");
             name = key.nextLine();
             seg = name.split(" ");

        }
    }

    public static class Database {
        String name;

        int firstindex, mDistance,  count;

        public Database(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<Database> RadixSort(ArrayList < Database > rData)
    {
        Integer max_count = 0, max_position = 0, max_minDist = 0;
        for (int i = 0; i < rData.size(); i++) {
            if (rData.get(i).count > max_count)
                max_count = rData.get(i).count;
            if (rData.get(i).firstindex > max_position)
                max_position = rData.get(i).firstindex;
            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<Database> 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<Database> 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<Database> 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<Database> 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;
    }
}