Minimum Edit Operations for String Transformation

Given two strings, an initial string and a target string, determine the minimum number of operations required to transform the initial string into the target string. You can perform the following operations:

1. (\textbf{Replace}): Replace the character at a given position with another character. Format: Replace i x indicates that the character at position (i) should be replaced by (x).

2. (\textbf{Insert}): Insert a new character at a given position. Format: Insert i x indicates that character (x) should be inserted at position (i).

3. (\textbf{Delete}): Delete the character at a given position. Format: Delete i indicates that the character at position (i) should be removed.

Note that the positions are 1-indexed. If the initial string is identical to the target string, no operations are needed. Use a dynamic programming approach (edit distance algorithm) to determine both the minimum number of operations and the precise sequence of operations required.

inputFormat

The input consists of two lines:\ The first line contains the initial string.\ The second line contains the target string.

outputFormat

Output the minimum number of operations on the first line.\ Then output each operation on a new line in the order they should be applied.## sample

kitten
sitting

3
Replace 1 s
Replace 5 i
Insert 7 g