Олимпиадный тренинг

Задача 28421. Damerau-Levenshtein distance


Задача

Темы:
One of the most common typing errors is the swapping of two adjacent characters, for example, instead of the word "program" the word "programma" is typed. The Levenshtein distance does not take into account such typos: when calculating the Levenshtein distance, one permutation will be counted as two edits (for example, deleting and inserting a character).
 
When calculating the Damerau-Levenshtein distance, in addition to the operations of replacing, inserting and deleting a character, the operation of permuting two neighboring characters is also allowed. At the same time, other characters cannot be inserted between the rearranged characters.
 
Determine the Damerau-Levenshtein distance for the two given strings.
 
Input Output
XABCDE
ACBYDF
4