import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */


/**
 *
 * @author Windows 10 Home
 */

class Node{
    int number_Match;
    int index_Match;
    int word_distace;

    String name_product;
    public Node(String name_product){
        this.name_product = name_product;

    }
}

public class Homework2 {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws FileNotFoundException {
        // TODO code application logic here

        int Show;
        if(args.length == 0){
            Show = 10;
        }else{
            Show = Integer.parseInt(args[0]);
        }

        Scanner s = new Scanner(new File("C:\\Users\\Windows 10 Home\\Documents\\NetBeansProjects\\Homework2\\src\\product.txt"));
        ArrayList<String> text_list = new ArrayList<String>();
        while(s.hasNextLine()){
            text_list.add(s.nextLine());
        }
        while(true){
            Scanner reader = new Scanner(System.in);
            System.out.print("Product Search - Input your keyword (s): ");
            String pattern_input = reader.nextLine();
            String[] pattern_parts = pattern_input.split(" ");

            long Start_time = System.currentTimeMillis();


            ArrayList<Node> Match = new ArrayList<>();
            for (int i=0; i<text_list.size();i++){
                Node get = new Node(text_list.get(i));
                ArrayList<Integer> Index = new ArrayList<Integer>();
                for (int j=0; j<pattern_parts.length;j++){
                    int found = KMP(text_list.get(i).toLowerCase().toCharArray(),pattern_parts[j].toLowerCase().toCharArray());
                    if(found != -1) {
                        Index.add(found);
                        if (j==0)
                            get.index_Match = found;
                            get.number_Match++;
                    }
                }
                Integer Min_distance = Integer.MAX_VALUE;
                for (int a = 0; a<Index.size(); a++){
                    for (int b=a+1; b<Index.size();b++){
                        if (Math.abs(Index.get(a)- Index.get(b)) < Min_distance ){
                            Min_distance = (Math.abs(Index.get(a)- Index.get(b)));
                        }
                    }
                    if(Min_distance > 100) Min_distance = 100;
                    get.word_distace = Min_distance;
                    Match.add(get);
                }

        }

            int[] Radix_int = new int[1000];
            String[] Radix_string = new String[1000];

            for(int i = 0;i<Match.size();i++){
                Radix_int[i] = ((10 - Match.get(i).number_Match)*1000) + (Match.get(i).index_Match*100) + (Match.get(i).word_distace);
                Radix_string[i] = Match.get(i).name_product;
            }

            int Match_count = Match.size();
            ArrayList<String> Show_name =  new ArrayList<String>();
            radix(Radix_int,Radix_int.length,Radix_string);
            String Check = "Check";
            System.out.println("Search Result is:");
            for(int i = 0;i<Radix_int.length;i++){
                if(Check == Radix_string[i]) Match_count--;
                if(Radix_int[i] != 0 && Check != Radix_string[i]){
                    Show_name.add(Radix_string[i]);
                    Check = Radix_string[i];
                }
            }

            int count=0;
            for(int i = 0;i<Show_name.size();i++){
                System.out.println("- " + Show_name.get(i));
                count++;
                if(count == Show) break;
            }

            System.out.println(Match_count + " product(s) matched ");
            long End_time = System.currentTimeMillis();
            long run_time = End_time - Start_time;
            System.out.println("run time: " + run_time + " ms");
        }

    }
    static int getMax(int arr[], int n)
    {
        int mx = arr[0];
        for (int i = 1; i < n; i++)
            if (arr[i] > mx)
                mx = arr[i];
        return mx;
    }

    static void countSort(int arr[], int n, int exp, String[] product)
    {
        int output[] = new int[n];
        String[] output2 = new String[n];

        int i;
        int count[] = new int[10];
        Arrays.fill(count,0);


        for (i = 0; i < n; i++)
            count[ (arr[i]/exp)%10 ]++;


        for (i = 1; i < 10; i++)
            count[i] += count[i - 1];


        for (i = n - 1; i >= 0; i--)
        {
            output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];
            output2[count[ (arr[i]/exp)%10 ] -1] = product[i];

            count[ (arr[i]/exp)%10 ]--;
        }


        for (i = 0; i < n; i++) {
            arr[i] = output[i];
            product[i] = output2[i];
        }
    }

    static void radix(int arr[], int n, String[] product)
    {

        int m = getMax(arr, n);


        for (int exp = 1; m/exp > 0; exp *= 10)
            countSort(arr, n, exp,product);
    }

    public static int BoyerMoore(char[ ] text, char[ ] pattern) {
        int n = text.length;
         int m = pattern.length;
         if (m == 0) return 0;
         Map<Character,Integer> last = new HashMap<>();
         for (int i=0; i < n; i++)
             last.put(text[i], -1);
         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]) {
                 if (k == 0) return i;
                 i--;
                 k--;
                 } else {
                 i += m - Math.min(k, 1 + last.get(text[i]));
                 k=m -1;
                 }
             }
         return -1;
         }

    public static int BruteForce(char[] text,char[] pattern){
        int n = text.length;
        int m = pattern.length;
        for(int i = 0; i <= n - m;i++){
            int k = 0;
            while(k < m && text[i+k] == pattern[k])
                k++;
            if(k == m)
                return i;
        }
        return -1;
    }

    public static int KMP(char[] text,char[] pattern){
        int n = text.length;
        int m = pattern.length;
        if(m == 0) return 0;
        int[] fail = computeFailKMP(pattern);
        int j = 0;
        int k = 0;
        while(j<n){
            if(text[j] == pattern[k]){
                if(k == m - 1)return j - m + 1;
                j++;
                k++;
            }else if(k>0){
                k = fail[k-1];
            }else{
                j++;
            }
        }
        return -1;
    }

   private static int[ ] computeFailKMP(char[ ] pattern) {
        int m = pattern.length;
        int[] fail = new int[m];
        int j = 1;
        int k = 0;
        while(j < m){
            if(pattern[j] == pattern[k]){
                fail[j] = k + 1;
                j++;
                k++;
            }else if(k > 0){
                k = fail[k - 1];
            }else{
                j++;
            }
        }
        return fail;
    }
}