Խմբագրման հեռավորություն (Edit Distance)
Խմբագրման հեռավորությունը երկու տողերի միջև այն նվազագույն գործողությունների (օպերացիաների) քանակն է, որոնք պահանջվում են մեկ տողը փոխակերպելու մյուսին։ Թույլատրելի գործողություններն են.
- Տողին մեկ նիշ ավելացնել
- Տողից մեկ նիշ हटացնել
- Տողի մեջ մեկ նիշ փոխարինել մեկ այլանիշով
Օրինակ, և տողերի խմբագրման հեռավորությունը 2 է, քանի որ կարելի է նախ ‘l’ տառը փոխարինել ‘m’-ով, ապա ավելացնել ‘i’ տառը։
Ձեզ խնդրում են գրել ծրագիր, որը ստանալով երկու տող, կհաշվի խմբագրման հեռավորությունը այդ տողերի միջև։
Մուտք
Մուտքի առաջին տողում գտնվում է առաջին տողը, իսկ երկրորդ տողում՝ երկրորդ տողը։ Երաշխավորվում է, որ տողերից ոչ մեկը չի պարունակում ավելի քան 1000 նիշ։
Ելք
Ծրագիրը ելքում պետք է տպի մեկ ամբողջ թիվ – տրված երկու տողերի խմբագրման հեռավորությունը։
Օրինակներ
Մուտք | Ելք |
love
movie | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB