Edit Distance with Custom Operations

You are given two strings, \(X[1\cdots m]\) and \(Y[1\cdots n]\), and a set of editing operations that transform a substring of \(X\) into \(Y\). The allowed operations and their costs are as follows:

• delete: Delete the first character of \(X\). Its cost is \(\mathrm{cost}(\mathtt{delete}) = 3\).
• replace: Replace the first character of \(X\) with any character (even the same one) and append it to the end of the target string. Its cost is \(\mathrm{cost}(\mathtt{replace}) = 6\).
• copy: Move (copy) the first character of \(X\) to the end of the target string without modifying it. This operation can only be applied if the character matches the corresponding character in \(Y\). Its cost is \(\mathrm{cost}(\mathtt{copy}) = 5\).
• insert: Insert a single character to the target string. Its cost is \(\mathrm{cost}(\mathtt{insert}) = 4\).
• twiddle: Swap the first two characters of \(X\) and append them (in swapped order) to the target string. This operation can be applied if \(X[i+1] = Y[j]\) and \(X[i] = Y[j+1]\) for the current positions. Its cost is \(\mathrm{cost}(\mathtt{twiddle}) = 4\).
• kill: After all other operations, delete the remaining suffix of \(X\) in one step. Its cost is given by
  \(\mathrm{cost}(\mathtt{kill}) = (\text{length of the remaining string}) \times \mathrm{cost}(\mathtt{delete}) - 1\).

The overall cost of a transformation is the sum of the operation costs used. For example, one way to convert algorithm into altruistic is:

The cost for this sequence computes as follows:

[ \begin{aligned} &3\times \mathrm{cost}(\mathtt{copy}) + 2\times \mathrm{cost}(\mathtt{replace}) + \mathrm{cost}(\mathtt{delete}) + 3\times \mathrm{cost}(\mathtt{insert}) \ &+ \mathrm{cost}(\mathtt{twiddle}) + \mathrm{cost}(\mathtt{kill}) \ =,& 3\times 5 + 2\times 6 + 3 + 3\times 4 + 4 + (1\times 3 - 1) \ =,& 48 \end{aligned} ]

Task: Given two strings \(X[1\cdots m]\) and \(Y[1\cdots n]\) and the costs provided, find the minimum edit cost required to convert \(X\) into \(Y\). You may assume that the final kill operation can be applied only once when \(Y\) has been completely formed.

inputFormat

The input consists of two lines:

• The first line contains the source string \(X\).
• The second line contains the target string \(Y\).

outputFormat

Output a single integer which is the minimum cost to transform \(X\) into \(Y\) using the given operations.

sample

algorithm
altruistic

48