PAL6_nevyreseneL

package pal;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    /*The task
     We say that a sequence of transformations producing W2 from W1 is optimal if there
     is not any shorter sequence producing W2 from W1. You are given a vocabulary and
     a bound on the number of single edit operations allowed per one transformation.
     To quantify how difficult assignments can be created, your task is to compute
     the maximum of lengths of all optimal sequences of transformations where the
     starting and target word can be chosen arbitrarily.

     Input
     The first line of the input contains two integers L, N separated by space. L is
     the maximal number of single edit operations allowed per one transformation.
     N is the number of words in the vocabulary. Next, there are N lines, each of
     them containing one word of the vocabulary. A word is a string having characters
     in the range 'a' - 'z'. The length of every word is at most 20 characters.
     The value of L does not exceed 5, the value of N does not exceed 5000.

     Output
     The output contains one text line with single integer representing the maximal
     length of optimal sequences of transformations.
     */
    public static int countOfEditOneTrans; //L - neni vyresena kontrola
    public static int countOfWords; //N
    public static String[] vocabulary;
    public static int[] dist;

    public static void main(String[] args) throws IOException {
        //args = new String[]{"pub10.in"};
        BufferedReader br = (args.length == 0)
                ? new BufferedReader(new InputStreamReader(System.in))
                : new BufferedReader(new InputStreamReader(new FileInputStream(args[0])));

        StringTokenizer configuration = new StringTokenizer(br.readLine());
        countOfEditOneTrans = Integer.parseInt(configuration.nextToken());
        countOfWords = Integer.parseInt(configuration.nextToken());
        vocabulary = new String[countOfWords];
        for (int i = 0; i < countOfWords; i++) {
            vocabulary[i] = br.readLine();
        }
        int optimal = findOptimal();
        System.out.println(optimal);

    }

    private static int computeDTW(String base, String compare) {
        int bLength = base.length() + 1;
        int cLength = compare.length() + 1;
        int[] DTWdist = new int[bLength]; //ceny transofmraci
        int[] DTWdisthelp = new int[bLength];
        int match; //shoda
        int insertion; //vlozeni
        int deletion; //smazani
        int replacement; //nahrazeni
        int[] temp;
        int count;
        //
        for (int b = 0; b < bLength; b++) {
            DTWdist[b] = b;
        }
        for (int c = 1; c < cLength; c++) {
            DTWdist[0] = c; //na zacatek nula, proto od indexu 1 a delky jsou +1
            count = 0;
            for (int b = 1; b < bLength; b++) {
                //pismenka se se shoduji
                if (base.charAt(b - 1) == compare.charAt(c - 1)) {
                    match = 0;
                } else {
                    match = 1;
                }
                //vypocty pro jednotlive operace - pricteme jim +1 a vybereme tu
                //nejmensi
                //kontrola L... ale je to blbost
                if (count < countOfEditOneTrans) {
                    replacement = DTWdist[b - 1] + match;
                    insertion = DTWdist[b] + 1;
                    deletion = DTWdisthelp[b - 1] + 1;
                    DTWdisthelp[b] = minimumCost(insertion, deletion, replacement);
                    count++;
                }
            }
            temp = DTWdist;
            DTWdist = DTWdisthelp;
            DTWdisthelp = temp;
        }
        return DTWdist[bLength - 1];
    }

    private static int findOptimal() {
        int[] distances = new int[countOfWords - 1];
        int sortedDistances[] = new int[countOfWords - 1];
        int[] higherDistances = new int[countOfWords - 1];
        for (int i = 0; i < countOfWords - 1; i++) {
            for (int j = i + 1; j < countOfWords; j++) {
                distances[i] = computeDTW(vocabulary[i], vocabulary[j]);
            }
            sortedDistances = countingSort(distances);
            higherDistances[i] = sortedDistances[countOfWords - 2];
        }
        higherDistances = countingSort(higherDistances);
        return higherDistances[countOfWords - 2];
    }

    private static int minimumCost(int a, int b, int c) {
        return Math.min(Math.min(a, b), c);
    }

    public static int[] countingSort(int[] array) {
        int[] sortedArray = new int[countOfWords - 1];
        int min = array[0];
        int max = array[0];
        for (int i = 1; i < countOfWords - 1; i++) {
            if (array[i] < min) {
                min = array[i];
            } else if (array[i] > max) {
                max = array[i];
            }
        }
        //histogram length from min to max
        int[] hist = new int[max - min + 1];
        for (int i = 0; i < countOfWords - 1; i++) {
            hist[array[i] - min]++;
        }
        //pole vyskytu
        hist[0]--;
        for (int i = 1; i < hist.length; i++) {
            hist[i] = hist[i] + hist[i - 1];
        }
        //min to max
        for (int i = countOfWords - 2; i >= 0; i--) {
            int histIndex = array[i] - min;
            int index = hist[histIndex];
            sortedArray[index] = array[i];
            hist[histIndex]--;
        }
        return sortedArray;
    }
}