Problem

2 /5


مسافة ليفنشتاين

Problem

إعطاء سلسلة نصية. يمكنك إجراء العمليات التالية باستخدامه:
& nbsp؛
1. استبدال حرف واحد من سلسلة بحرف آخر.
& nbsp؛
2. حذف حرف تعسفي واحد.
& nbsp؛
3. أدخل حرفًا عشوائيًا في موضع عشوائي في السلسلة.
& nbsp؛
على سبيل المثال ، استخدام العملية الأولى من السلسلة & quot؛ JUICE & quot؛ يمكنك الحصول على السلسلة & quot؛ SUK & quot؛ باستخدام العملية الثانية - السلسلة & quot؛ OK & quot ؛، باستخدام العملية الثالثة - السلسلة & quot؛ STOCK.
& nbsp؛
الحد الأدنى لعدد مثل هذه العمليات التي يمكن استخدامها للحصول على سلسلة أخرى من سلسلة واحدة يسمى تكلفة التحرير أو مسافة Levenshtein.
& nbsp؛
أوجد مسافة Levenshtein للسلسلتين المحددتين.
& nbsp؛
إدخال
يتلقى البرنامج سلسلتين كمدخلات ، لا يتجاوز طول كل منهما 1000 حرف ، وتتألف السلاسل من أحرف لاتينية كبيرة فقط.
& nbsp؛
الإخراج
مطلوب لإخراج رقم واحد & ndash؛ مسافة ليفنشتاين لسلاسل معينة.
نبسب ؛ <الجسم>
إدخال الإخراج
ABCDEFGH
ACDEXGIH
3

نبسب ؛

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!