Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package com.company;
- import java.io.File;
- import java.io.IOException;
- import java.io.PrintWriter;
- import java.util.Scanner;
- public class Main {
- public static void main(String[] args) throws IOException {
- Scanner sc = new Scanner(new File("input.txt"));
- PrintWriter pw = new PrintWriter(new File("output.txt"));
- // Scanner sc = new Scanner(System.in);
- //считываем данные
- String s1 = sc.nextLine();
- String s2 = sc.nextLine();
- int len1 = s1.length();
- int len2 = s2.length();
- int[][] dp = new int[len1+1][len2+1];
- //заполняем i-ые строки и столбцы
- dp[0][0] = 0;
- // for (int i = 0; i<=len1; i++)
- // dp[0][i] = i;
- // for (int i = 0; i<=len2; i++)
- // dp[i][0] = i;
- for (int i = 1; i<=len1; i++)
- dp[0][i] = i;
- //динамика по формуле Вагнера-Фишера
- for (int i = 1; i<=len1; i++) {
- dp[i][0] = i;
- for (int j = 1; j <= len2; j++) {
- if (s1.charAt(i - 1) != s2.charAt(j - 1)) {
- int min = Math.min(dp[i-1][j-1] + 1, dp[i-1][j] + 1);
- if (min < dp[i][j-1]+1)
- dp[i][j] = min;
- else
- dp[i][j] = dp[i][j-1]+1;
- } else
- dp[i][j] = dp[i - 1][j - 1];
- }
- }
- pw.println(dp[len1][len2]);
- pw.close();
- sc.close();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement