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(" ");
        long start1 = System.currentTimeMillis();
        //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(" ");*/
       // }
        long end1 = System.currentTimeMillis();
        System.out.println("BM_Time : "+ (end1-start1)+" (ms)");

        long start2 = System.currentTimeMillis();
        ArrayList<Database> Keep2 = new ArrayList<>();
        for (int j = 0; j < list.size(); j++) {
            Database Store2 = new Database(list.get(j));
            ArrayList<Integer> Index = new ArrayList<Integer>();
            for (int k = 0; k < seg.length; k++) {
                if (findBrute(list.get(j).toUpperCase().toCharArray(), seg[k].toUpperCase().toCharArray()) != -1) {
                    Index.add(findBrute(list.get(j).toUpperCase().toCharArray(), seg[k].toUpperCase().toCharArray()));
                    if (Store2.count==0) {
                        Store2.firstindex = findBrute(list.get(j).toUpperCase().toCharArray(), seg[k].toUpperCase().toCharArray());
                        Store2.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))));
                    }
                }
                Store2.mDistance = min;
            }
            Keep2.add(Store2);
            // System.out.println(Store);
        }
        int note2 = 0;
        List<Database> S2 = RadixSort(Keep2);
        int z2=0;
        while (z2<S2.size())
        {
            if (S2.get(z2).firstindex > 1000)
            {
                z2=0;

                break;
            }
            note2 = z2;
            z2++;
        } note2++;

        if(note2 > input)
        {
            note2 = input;
        }
        if (note2 ==  1)
        {
            note2=0;
        }
        long end2 = System.currentTimeMillis();
        System.out.println("BF_Time : "+(end2-start2)+" (ms)");



        long start3 = System.currentTimeMillis();
        ArrayList<Database> Keep3 = new ArrayList<>();
        for (int j = 0; j < list.size(); j++) {
            Database Store3 = new Database(list.get(j));
            ArrayList<Integer> Index = new ArrayList<Integer>();
            for (int k = 0; k < seg.length; k++) {
                if (findKMP(list.get(j).toUpperCase().toCharArray(), seg[k].toUpperCase().toCharArray()) != -1) {
                    Index.add(findKMP(list.get(j).toUpperCase().toCharArray(), seg[k].toUpperCase().toCharArray()));
                    if (Store3.count==0) {
                        Store3.firstindex = findKMP(list.get(j).toUpperCase().toCharArray(), seg[k].toUpperCase().toCharArray());
                        Store3.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))));
                    }
                }
                Store3.mDistance = min;
            }
            Keep3.add(Store3);
            // System.out.println(Store);
        }
        int note3 = 0;
        List<Database> S3 = RadixSort(Keep2);
        int z3=0;
        while (z3<S3.size())
        {
            if (S3.get(z3).firstindex > 1000)
            {
                z3=0;

                break;
            }
            note3 = z3;
            z3++;
        } note3++;

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


        long end3 = System.currentTimeMillis();
        System.out.println("KMP_Time : "+(end3-start3)+" (ms)");






    }

    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;
    }
    private static int[ ] computeFailKMP(char[ ] pattern) {  int m = pattern.length;
         int[ ] fail = new int[m]; // by default, all overlaps are zero
         int j = 1;
         int k = 0;
         while (j < m) { // compute fail[j] during this pass, if nonzero
             if (pattern[j] == pattern[k]) { // k + 1 characters match thus far
                fail[j] = k + 1;
                 j++;
                 k++;
                } else if (k > 0) // k follows a matching prefix
                 k = fail[k-1];
             else // no match found starting at j
             j++;
            }  return fail;
        }

    public static int findBrute(char[ ] text, char[ ] pattern) {  int n = text.length;
         int m = pattern.length;
         for (int i=0; i <= n - m; i++) { // try every starting index within text
             int k = 0; // k is index into pattern
             while (k < m && text[i+k] == pattern[k]) // kth character of pattern matches
                 k++;
            if (k == m) // if we reach the end of the pattern,
                 return i; // substring text[i..i+m-1] is a match
             }  return -1; // search failed
         }

    public static int findKMP(char[ ] text, char[ ] pattern) {  int n = text.length;
         int m = pattern.length;
         if (m == 0) return 0; // trivial search for empty string
         int[ ] fail = computeFailKMP(pattern); // computed by private utility
         int j = 0; // index into text
         int k = 0; // index into pattern
         while (j < n) {  if (text[j] == pattern[k]) { // pattern[0..k] matched thus far
             if (k == m - 1) return j - m + 1; // match is complete
             j++; // otherwise, try to extend match
             k++;
             } else if (k > 0)
             k = fail[k-1]; // reuse suffix of P[0..k-1]
             else
             j++;
             }  return -1; // reached end without match
         }

    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;
    }
}