/ / / /

Java


import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;


class Prescription {
	public String route;
	public int distance;
	Prescription(int distance, String route) {
		this.distance = distance;
		this.route = route;
	}
}
/**
 * @author gvsmirnov
 */
class Levenshtein {
	/**
	 * Calculates Edit Distance between S1 and S2 and the prescription 
* Consumes O(n2) memory and runs in O(n2) time,
* Where n is the length of the biggest string * @param S1 - first input string * @param S2 - second input string * @return Prescription - the edit distance and the path retraced */ public static Prescription Levenshtein1(String S1, String S2) { int m = S1.length(), n = S2.length(); int[][] D = new int[m + 1][n + 1]; char[][] P = new char[m + 1][n + 1]; // First fill the basic values for (int i = 0; i <= m; i++) { D[i][0] = i; P[i][0] = 'D'; } for (int i = 0; i <= n; i++) { D[0][i] = i; P[0][i] = 'I'; } for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) { int cost = (S1.charAt(i - 1) != S2.charAt(j - 1)) ? 1 : 0; if(D[i][j - 1] < D[i - 1][j] && D[i][j - 1] < D[i - 1][j - 1] + cost) { //Inserting D[i][j] = D[i][j - 1] + 1; P[i][j] = 'I'; } else if(D[i - 1][j] < D[i - 1][j - 1] + cost) { //Deleting D[i][j] = D[i - 1][j] + 1; P[i][j] = 'D'; } else { //Doing nothing or replacing D[i][j] = D[i - 1][j - 1] + cost; P[i][j] = (cost == 1) ? 'R' : 'M'; } } //Retracing StringBuilder route = new StringBuilder(""); int i = m, j = n; do { char c = P[i][j]; route.append(c); if(c == 'R' || c == 'M') { i --; j --; } else if(c == 'D') { i --; } else { j --; } } while((i != 0) && (j != 0)); return new Prescription(D[m][n], route.reverse().toString()); } /** * Calculates Edit Distance between S1 and S2 and the prescription
* Consumes O(n) memory and runs in O(n3) time,
* Where n is the length of the biggest string * @param S1 - first input string * @param S2 - second input string * @return Prescription - the edit distance and the path retraced */ public static Prescription Levenshtein2(String S1, String S2) { int m = S1.length(), n = S2.length(); int[] D1 = new int[n + 1]; int[] D2 = new int[n + 1]; char[] P1 = new char[n + 1]; char[] P2 = new char[n + 1]; int d = 0; StringBuilder route = new StringBuilder(""); int iPos = m, jPos = n; do { for(int i = 0; i <= jPos; i ++) D2[i] = i; for(int i = 1; i <= iPos; i ++) { D1 = D2; D2 = new int[jPos + 1]; P1 = P2; P2 = new char[jPos + 1]; for(int j = 0; j <= jPos; j ++) { if(j == 0) D2[j] = i; else { int cost = (S1.charAt(i - 1) != S2.charAt(j - 1)) ? 1 : 0; if(D2[j - 1] < D1[j] && D2[j - 1] < D1[j - 1] + cost) { //Inserting D2[j] = D2[j - 1] + 1; P2[j] = 'I'; } else if(D1[j] < D1[j - 1] + cost) { //Deleting D2[j] = D1[j] + 1; P2[j] = 'D'; } else { //Doing nothing or replacing D2[j] = D1[j - 1] + cost; P2[j] = (cost == 1) ? 'R' : 'M'; } } } } if(iPos == m && jPos == n) d = D2[n]; //Tracing all actions in the last two rows int _iPos = iPos; while(iPos >= _iPos - 1 && iPos !=0 && jPos != 0) { char c = (iPos == _iPos) ? P2[jPos] : P1[jPos]; route.append(c); if(c == 'R' || c == 'M') { iPos --; jPos --; } else if(c == 'D') { iPos --; } else { jPos --; } } } while((iPos != 0) && (jPos != 0)); return new Prescription(d, route.reverse().toString()); } /** * Calculates Edit Distance between S1 and S2 and the prescription
* Consumes O(n1.5) memory and runs in O(n2.5) time,
* Where n is the length of the biggest string * @param S1 - first input string * @param S2 - second input string * @return Prescription - the edit distance and the path retraced */ public static Prescription Levenshtein3(String S1, String S2) { int m = S1.length(), n = S2.length(); int h = (int)Math.sqrt(m + 1); int[][] D = new int[h + 1][n + 1]; char[][] P = new char[h + 1][n + 1]; int d = 0; StringBuilder route = new StringBuilder(""); int iPos = m, jPos = n; do { for (int i = 0; i <= jPos; i++) { D[0][i] = i; P[0][i] = 'I'; } int _i = 1; for(int i = 1; i <= iPos; i ++) { for(int j = 0; j <= jPos; j ++) { if(j == 0) D[_i][j] = i; else { int cost = (S1.charAt(i - 1) != S2.charAt(j - 1)) ? 1 : 0; if(D[_i][j - 1] < D[_i - 1][j] && D[_i][j - 1] < D[_i - 1][j - 1] + cost) { //Inserting D[_i][j] = D[_i][j - 1] + 1; P[_i][j] = 'I'; } else if(D[_i - 1][j] < D[_i - 1][j - 1] + cost) { //Deleting D[_i][j] = D[_i - 1][j] + 1; P[_i][j] = 'D'; } else { //Doing nothing or replacing D[_i][j] = D[_i - 1][j - 1] + cost; P[_i][j] = (cost == 1) ? 'R' : 'M'; } } } if(i % h == 0) { //Allocate memory for the new row and put the previous' last line as this one's first int[] vRow = new int[n + 1]; char[] cRow = new char[n + 1]; for(int j = 0; j <= n; j ++) { vRow[j] = D[_i][j]; cRow[j] = P[_i][j]; } D = new int[h + 1][n + 1]; P = new char[h + 1][n + 1]; for(int j = 0; j <= n; j ++) { D[0][j] = vRow[j]; P[0][j] = cRow[j]; } _i = 0; } _i++; } if(iPos == m && jPos == n) d = D[_i - 1][n]; //Tracing all actions in the last _i - 1 rows while(_i > 0 && iPos !=0 && jPos != 0) { char c = P[_i - 1][jPos]; route.append(c); if(c == 'R' || c == 'M') { iPos --; jPos --; _i --; } else if(c == 'D') { iPos --; _i --; } else { jPos --; } } } while((iPos != 0) && (jPos != 0)); return new Prescription(d, route.reverse().toString()); } } public class editdist implements Runnable { BufferedReader in; PrintWriter out; static int mode; public static void main(String[] args) { mode = -1*Integer.parseInt(args[0]); new Thread(new editdist()).run(); } public void run() { try { in = new BufferedReader(new FileReader("editdist.in")); out = new PrintWriter(new FileWriter("editdist.out")); solve(); } catch (Exception e) { e.printStackTrace(); } finally { out.close(); } } void solve() throws NumberFormatException, IOException { //long t1,t2; Prescription result = new Prescription(-1, ""); String S1 = in.readLine(); String S2 = in.readLine(); /*t1 = System.nanoTime(); result = Levenshtein.Levenshtein1(S1, S2); t2 = System.nanoTime(); System.out.println(result.distance); //System.out.println(result.route); System.out.println((t2 - t1)/1000000 + " msec."); t1 = System.nanoTime(); result = Levenshtein.Levenshtein2(S1, S2); t2 = System.nanoTime(); System.out.println("---"); System.out.println(result.distance); //System.out.println(result.route); System.out.println((t2 - t1)/1000000 + " msec."); t1 = System.nanoTime(); result = Levenshtein.Levenshtein3(S1, S2); t2 = System.nanoTime(); System.out.println("---"); System.out.println(result.distance); //System.out.println(result.route); System.out.println((t2 - t1)/1000000 + " msec.");*/ switch(mode) { case 1: result = Levenshtein.Levenshtein1(S1, S2); break; case 2: result = Levenshtein.Levenshtein2(S1, S2); break; case 3: result = Levenshtein.Levenshtein3(S1, S2); break; default: System.out.println("run editdist -n, where n is from 1 to 3"); } if(result.distance != -1) { System.out.println(result.distance); out.println(result.distance); out.println(result.route); } } }