leven

package textsearch;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map.Entry;
import java.util.Queue;
import java.util.Set;
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 max = 0;

    public static HashMap<Node, Set<Node>> LevGraph;

    public static void main(String[] args) throws IOException {
       // args = new String[]{"pub03.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];
        LevGraph = new HashMap<>();
        for (int i = 0; i < countOfWords; i++) {
            add(new Node(br.readLine()));
        }
        //  printGraph();
        for (Node n : LevGraph.keySet()) {
            if (n.depth == -1) {
                n.depth = 0;
                BFS(n);
            }
        }

        System.out.println(max);
    }

    private static int computeDTW(Node base, Node compare) {
        int bLength = base.word.length() + 1;
        int cLength = compare.word.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;

        for (int b = 0; b < bLength; b++) {
            DTWdist[b] = b;
        }
        for (int c = 1; c < cLength; c++) {
            DTWdisthelp[0] = c; //na zacatek nula, proto od indexu 1 a delky jsou +1
            for (int b = 1; b < bLength; b++) {
                //pismenka se se shoduji
                if (base.word.charAt(b - 1) == compare.word.charAt(c - 1)) {
                    match = 0;
                } else {
                    match = 1;
                }
                //vypocty pro jednotlive operace - pricteme jim +1 a vybereme tu
                insertion = DTWdist[b] + 1;
                replacement = DTWdist[b - 1] + match;
                deletion = DTWdisthelp[b - 1] + 1;
                DTWdisthelp[b] = minimumCost(insertion, deletion, replacement);
            }
            temp = DTWdist;
            DTWdist = DTWdisthelp;
            DTWdisthelp = temp;
        }
        return DTWdist[bLength - 1];
    }

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

    private static void add(Node n) {
        int levDist;
        if (LevGraph.containsKey(n) == false) {
            LevGraph.put(n, new HashSet<Node>());
        }
        for (Node s : LevGraph.keySet()) {
            //splnena podminka poctu operaci, udelame propojeni
            levDist = computeDTW(n, s);
            if (n.equals(s) == false && levDist <= countOfEditOneTrans) {
                if (!LevGraph.containsKey(s)) {
                    LevGraph.put(s, new HashSet<Node>());
                }
                LevGraph.get(n).add(s);
                LevGraph.get(s).add(n);
            }
        }
    }

    private static void BFS(Node root) {
        Queue<Node> q = new LinkedList<Node>();
        q.add(root);
        while (!q.isEmpty()) {
            Node t = q.remove();
            if (t.depth > max) {
                max = t.depth;
            }
            for (Node s : LevGraph.get(t)) {
                if (s.depth == -1) {
                    s.depth = t.depth + 1;
                    q.add(s);
                }
            }
        }
        clearDepth();
    }

    private static void clearDepth() {
        for (Node n : LevGraph.keySet()) {
            n.depth = -1;
        }
    }

    //nonused
    private static void printGraph() {
        for (Entry<Node, Set<Node>> entry : LevGraph.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue().toString());
        }
    }

    private static class Node {

        int depth;
        String word;

        public Node(String word, int depth) {
            this.depth = depth;
            this.word = word;
        }

        public Node(String word) {
            this.depth = -1;
            this.word = word;
        }

        @Override
        public String toString() {
            return "word " + this.word + "- " + this.depth;
        }
    }
}