Module: En büyük ortak alt dizi


Problem

2 /5


Levenshtein mesafesi

Problem

Verilen bir metin dizisi. Bununla aşağıdaki işlemleri gerçekleştirebilirsiniz:
 
1. Bir dizgenin bir karakterini başka bir karakterle değiştirin.
 
2. Rastgele bir karakteri silin.
 
3. Dizede isteğe bağlı bir konuma isteğe bağlı bir karakter ekleyin.
 
Örneğin, "JUICE" "SUK" dizesini ikinci işlemi - "OK" dizesini kullanarak, üçüncü işlemi - "STOCK" dizesini kullanarak elde edebilirsiniz.
 
Bir diziden başka bir dizi elde etmek için kullanılabilecek bu tür işlemlerin minimum sayısına düzenleme maliyeti veya Levenshtein mesafesi denir.
 
Verilen iki dizi için Levenshtein mesafesini bulun.
 
Giriş
Program girdi olarak her birinin uzunluğu 1000 karakteri geçmeyen iki dizi alır, diziler yalnızca büyük latin harflerden oluşur.
 
Çıktı
Tek bir sayı çıktısı almak için gereklidir – Verilen diziler için Levenshtein mesafesi.
 
 

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!

Giriş Çıktı
ABCDEFGH
ACDEXGIH
 3