Shortest Superstring problem, with graph, KMP and Hamiltonia

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

/**
 * Este algortimo esta basado en el trabajo de Tesis, de katarina Martinova de la universidad
 * Masarykova, llamado Algorithms for shortest superstring problems de 2014.
 *
 *
 * @author js.prieto10
 */
public class ProblemaC {

    private List<String> strings;
    private String superstring;
    private List<String> nodes;
    private int totalLength;

    /**
     * constructor
     *
     * @param words set de palabras
     * @param tamaño total de todas las palabras del set
     */
    public ProblemaC(List<String> words, int totalLength) {
        strings = words;
        this.totalLength = totalLength;
        nodes = new ArrayList<>();
    }


    public String getSuperstring() {
        return superstring;
    }


    /**
     * Generación de arcos con pesos a partir Knuth-Morris-Pratt string matching algorithm
     *
     * @param List, la lista de nodos del grafo
     * @return arcos del grafo
     */
    protected List<Edge> countWeights(List<String> nodes) {

        List<Edge> edges = new ArrayList<>();
        String textString;
        String patternString;
        int l = 0;

        int state;
        String overlap;

        for (int pattern = 1; pattern < nodes.size(); pattern++) {
            patternString = nodes.get(pattern);

            for (int text = 0; text < nodes.size() - 1; text++) {
                if (text == pattern) {
                    continue;
                }
                if (text == 0 || pattern == nodes.size() - 1) {
                    edges.add(new Edge(text, pattern, 0, Edge.Status.FREE));
                    continue;
                }
                textString = nodes.get(text);
                if ((l = textString.length()) > patternString.length()) {
                    textString = textString.substring(l - patternString.length(), l);
                }
                state = patternString.length();
                overlap = patternString;
                while (true) {
                    if (state == 0) {
                        break;
                    }
                    if (textString.endsWith(overlap)) {
                        break;
                    } else {
                        state--;
                        overlap = overlap.substring(0, state);
                    }
                }
                edges.add(new Edge(text, pattern, state, Edge.Status.FREE));
            }
        }
        return edges;
    }

    /**
     * inserta los nodos en un "bucket" de manera descendente
     *
     * @param list, (bucket)
     * @param e edge to be inserted
     */
    protected void decInsertionSort(List<Edge> list, Edge e) {
        if (list.isEmpty()) {
            list.add(e);
            return;
        }
        for (int i = 0; i < list.size(); i++) {
            if (e.getWeight() >= list.get(i).getWeight()) {
                list.add(i, e);
                break;
            }
            if (i == list.size() - 1) {
                list.add(e);
            }
        }
    }

    /**
     * splits edges into buckets, buckets are sortet in decreasing order buckets
     * are concatenated in opposite order into resulting sorted list of edges
     *
     * @param edges, lista de arcos
     * @param maxValue, tamaño total de todos lo strings de la lista
     * @return sorted list of edges
     */
    protected List<Edge> bucketSort(List<Edge> edges, int maxValue) {
        int number;
        number = edges.size();
        int zeros;
        zeros = 2 * strings.size() + 1;
        int bucketNum;
        bucketNum = number / zeros;
        if (number % zeros > 0) {
            bucketNum++;
        }
        int range;
        if (bucketNum == 1) {
            range = maxValue;
        } else {
            range = maxValue / (bucketNum - 1);
        }
        List<Edge>[] buckets;
        buckets = new List[bucketNum];
        for (int i = 0; i < bucketNum; i++) {
            buckets[i] = new ArrayList<>();
        }
        int limit;
        for (Edge e : edges) {
            if (e.getWeight() == 0) {
                buckets[0].add(e);
                continue;
            }
            limit = 0;
            for (int i = 1; i < bucketNum; i++) {
                if (i == bucketNum - 1) {
                    limit = maxValue;
                } else {
                    limit += range;
                }
                if (e.getWeight() <= limit) {
                    decInsertionSort(buckets[i], e);
                    break;
                }
            }
        }

        List<Edge> orderedEdges = new ArrayList<>();
        for (int i = bucketNum - 1; i > -1; i--) {
            orderedEdges.addAll(buckets[i]);
        }
        return orderedEdges;
    }

    /**
     * conecta las arcos del camino que pueden ser conectados
     *
     * @param path, camino hamiltoiano
     */
    protected void organizePath(List<Edge> path) {
        if (path.size() <= 1) {
            return;
        }
        List<Integer> starts = new ArrayList<>();
        starts.add(0);
        List<Integer> ends = new ArrayList<>();
        for (int i = 0; i < path.size(); i++) {
            if (i == path.size() - 1) {
                ends.add(i);
                break;
            }
            if (path.get(i).getEnd() != path.get(i + 1).getStart()) {
                ends.add(i);
                starts.add(i + 1);
            }
        }
        if (starts.size() == 1) {
            return;
        }
        for (int i = 0; i < starts.size(); i++) {
            for (int j = 0; j < ends.size(); j++) {
                if (i == j) {
                    continue;
                }
                if (path.get(starts.get(i)).getStart() == path.get(ends.get(j)).getEnd()) {
                    if (ends.get(j) < starts.get(i)) {
                        List<Edge> selection = path.subList(starts.get(i), ends.get(i) + 1);
                        int length = selection.size();
                        path.addAll(ends.get(j) + 1, selection);
                        path.subList(starts.get(i) + length, ends.get(i) + 1 + length).clear();
                        return;
                    } else {
                        List<Edge> selection = path.subList(starts.get(j), ends.get(j) + 1);
                        int length = selection.size();
                        path.addAll(starts.get(i), selection);
                        path.subList(starts.get(j) + length, ends.get(j) + 1 + length).clear();
                        return;
                    }
                }
            }
        }
    }

    /**
     * inserta un nuevo arco al caminimo hamiltoiano
     *
     * @param path, camino hamiltoniano parcial
     * @param e, arco ha ser insertado
     */
    protected void addToHamPath(List<Edge> path, Edge e) {
        if (path.isEmpty()) {
            path.add(e);
            return;
        }
        if (e.getStart() == 0) {
            path.add(0, e);
            return;
        }

        for (int i = 0; i < path.size(); i++) {
            if (path.get(i).getEnd() == e.getStart()) {
                path.add(i + 1, e);
                return;
            }
            if (e.getEnd() == path.get(i).getStart()) {
                path.add(i, e);
                return;
            }
        }
        path.add(e);
    }

    /**
     *
     *
     * @param path, camino hamiltoniano parcial
     * @param e, ultimo arco insertado
     * @return el valor final parcial
     */
    protected int getPartEnd(List<Edge> path, Edge e) {
        if (path.size() == 1) {
            return e.getEnd();
        }
        int index = path.indexOf(e);
        int end = e.getEnd();
        for (int i = index; i < path.size(); i++) {
            if (i == path.size() - 1) {
                return path.get(path.size() - 1).getEnd();
            }
            if ((end = path.get(i).getEnd()) != path.get(i + 1).getStart()) {
                break;
            }
        }
        return end;
    }

    /**
     *
     * @param path, camino hamiltiano parcial
     * @param e, ultimo nodo en ser insertado
     * @return el valor inicial del camino
     */
    protected int getPartStart(List<Edge> path, Edge e) {
        if (path.size() == 1) {
            return e.getStart();
        }
        int index = path.indexOf(e);
        int start = e.getStart();
        for (int i = index; i > -1; i--) {
            if (i == 0) {
                return path.get(0).getStart();
            }
            if ((start = path.get(i).getStart()) != path.get(i - 1).getEnd()) {
                break;
            }
        }
        return start;
    }

    /**
     * algoritmo para hallar el camino hamiltiano
     *
     * @param edges, lista de arcos
     * @return El camino hamiltiano más largo
     */
    protected List<Edge> hamPath(List<Edge> edges) {
        List<Edge> path = new ArrayList<>();
        int partStart = -1;
        int partEnd = -1;
        for (Edge edge : edges) {
            if (!edge.getStatus().equals(Edge.Status.FREE)) {
                continue;
            }
            edge.setStatus(Edge.Status.NOT_FREE);
            addToHamPath(path, edge);
            organizePath(path);

            partStart = getPartStart(path, edge);
            partEnd = getPartEnd(path, edge);

            for (Edge e : edges) {
                if (e.getStart() == partEnd && e.getEnd() == partStart) {
                    e.setStatus(Edge.Status.MAKING_CIRCLE);
                    continue;
                }
                if (e.getStart() == edge.getEnd() && e.getEnd() == edge.getStart()) {
                    e.setStatus(Edge.Status.MAKING_CIRCLE);
                    continue;
                }
                if (edge.getStart() == e.getStart()) {
                    e.setStatus(Edge.Status.NOT_FREE);
                    continue;
                }
                if (edge.getEnd() == e.getEnd()) {
                    e.setStatus(Edge.Status.NOT_FREE);
                }

            }
        }
        return path;
    }

    /**
     * Crea un superstring a partir del camino hamiltiano generado
     *
     * @param path, camino hamiltiano
     * @return superstring
     */
    protected String buildSuperstring(List<Edge> path) {
        String string = nodes.get(path.get(0).getStart());
        for (int i = 0; i < path.size(); i++) {
            string = string + nodes.get(path.get(i).getEnd()).substring(path.get(i).getWeight());
        }
        return string;
    }

    public void run() {
        List<Edge> edges;
        List<Edge> path;

        nodes.add(""); // añadir un nodo inicial
        nodes.addAll(strings); // añada toda la lista de nodos
        nodes.add(""); // añade un nodo final
        edges = countWeights(nodes); // crea los arcos con peso dado al algoritmo KMP string matching
        edges = bucketSort(edges, totalLength); // ordena los arcos de manera decreciente
        path = hamPath(edges); // genera el camino hamiltiano
        superstring = buildSuperstring(path); // crea un superstring a partir del camino hamiltoniano.

    }

    /**
     *  Clase arco, para la creación de un grafo dirigido con peso.
     */
    public static class Edge {

        public enum Status {FREE, NOT_FREE, MAKING_CIRCLE}

        private int start;
        private int end;
        private int weight;
        private Status status;

        public Edge(int start, int end, int weight, Status status) {
            this.start = start;
            this.end = end;
            this.weight = weight;
            this.status = status;
        }

        public int getStart() {
            return start;
        }

        public void setStart(int start) {
            this.start = start;
        }

        public int getEnd() {
            return end;
        }

        public void setEnd(int end) {
            this.end = end;
        }

        public int getWeight() {
            return weight;
        }

        public void setWeight(int weight) {
            this.weight = weight;
        }

        public Status getStatus() {
            return status;
        }

        public void setStatus(Status status) {
            this.status = status;
        }

        @Override
        public String toString() {
            return "[" + start + ", " + end + ", " + weight + ", " + status + "]";
        }

    }

    public static void main(String arg[]) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String lineain;
        String data[];
        List<String> fragments;
        ProblemaC superStringCreator;
        int n;
        int k;

        while (true){
            fragments = new ArrayList<String>();
            lineain = br.readLine();
            if (lineain.isEmpty()) return;
            data = lineain.split(" ");
            n = Integer.parseInt(data[0]);
            k = Integer.parseInt(data[1]);
            for (int i = 0; i != n; i++) {
                lineain = br.readLine();
                fragments.remove(lineain);
                fragments.add(lineain);

            }
            superStringCreator = new ProblemaC(fragments, k);
            superStringCreator.run();
            System.out.println(superStringCreator.getSuperstring() );
        }

    }

}