Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package pal;
- 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.Map.Entry;
- 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[][] dist;
- public static HashMap<String, Set<Word>> LevGraph;
- public static Set<Integer> dijkstraQ;
- 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(br.readLine());
- }
- printGraph();
- }
- 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;
- 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.charAt(b - 1) == compare.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(String word) {
- int levDist;
- if (LevGraph.containsKey(word) == false) {
- LevGraph.put(word, new HashSet<>());
- }
- for (String s : LevGraph.keySet()) {
- //splnena podminka poctu operaci, udelame propojeni
- levDist = computeDTW(word, s);
- if (word.equals(s) == false && levDist <= countOfEditOneTrans) {
- if (!LevGraph.containsKey(s)) {
- LevGraph.put(s, new HashSet<>());
- }
- LevGraph.get(word).add(new Word(s, levDist));
- LevGraph.get(s).add(new Word(word, levDist));
- }
- }
- }
- private static class Word {
- int levDist;
- String word;
- public Word(String word, int levDist) {
- this.levDist = levDist;
- this.word = word;
- }
- @Override
- public String toString() {
- return "word " + this.word + " L: " + this.levDist + " ";
- }
- }
- public static void printGraph() {
- for (Entry<String, Set<Word>> entry : LevGraph.entrySet()) {
- System.out.println(entry.getKey() + ": " + entry.getValue().toString());
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement