Module: Susulan biasa yang paling hebat


Problem

2 /5


Jarak Levenshtein

Problem

Diberi rentetan teks. Anda boleh melakukan operasi berikut dengannya:
 
1. Gantikan satu aksara rentetan dengan aksara lain.
 
2. Padamkan satu aksara sewenang-wenangnya.
 
3. Sisipkan aksara arbitrari pada kedudukan arbitrari dalam rentetan.
 
Sebagai contoh, menggunakan operasi pertama daripada rentetan "JUICE" anda boleh mendapatkan rentetan "SUK", menggunakan operasi kedua - rentetan "OK", menggunakan operasi ketiga - rentetan "STOCK.
 
Bilangan minimum operasi sedemikian yang boleh digunakan untuk mendapatkan yang lain daripada satu rentetan dipanggil kos pengeditan atau jarak Levenshtein.
 
Cari jarak Levenshtein untuk dua rentetan yang diberikan.
 
Input
Atur cara menerima dua rentetan sebagai input, panjang setiap satunya tidak melebihi 1000 aksara, rentetan hanya terdiri daripada huruf latin besar.
 
Output
Diperlukan untuk mengeluarkan satu nombor – Jarak Levenshtein untuk rentetan yang diberikan.
 
 

time 1500 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

Input Output
ABCDEFGH
ACDEXGIH
 3