Minimum Operations to Transform Strings

You are given a target string S and a collection of n strings. Your task is to compute the minimum number of operations required to transform each string in the collection into S. The allowed operations are insertion, deletion, or substitution of a single character.

The problem is a classic edit distance problem. The recurrence relation for computing the edit distance between two strings a and b is given by:

\( dp[i][j] = \begin{cases} j & \text{if } i=0,\\ i & \text{if } j=0,\\ dp[i-1][j-1] & \text{if } a[i-1]=b[j-1],\\ 1 + \min\{ dp[i-1][j],\; dp[i][j-1],\; dp[i-1][j-1] \} & \text{otherwise}.\end{cases} \)

Your program should read from the standard input and output the answer to the standard output.

inputFormat

The input is given via STDIN in the following format:

1. An integer n representing the number of strings in the collection.
2. A string S representing the target string.
3. Next n lines, each containing a single string from the collection.

outputFormat

Output a single line to STDOUT containing n integers separated by a space. Each integer represents the minimum number of operations required to transform the corresponding string from the collection into S.

3
abc
ab
abcd
xyz

1 1 3