Minimum Operations to Match Pattern

You are given two strings, s and p. Your task is to determine the minimum number of operations needed to modify a contiguous substring of s so that it exactly matches the pattern p. In one operation, you may replace any single character in s with any other character.

Formally, let n be the length of s and m be the length of p. For each valid index i (with 0 ≤ i ≤ n - m), consider the substring \(s[i : i+m]\). Define the number of differences \(d_i\) as follows:

[ \displaystyle d_i = \sum_{j=0}^{m-1} \mathbf{1}_{{s[i+j] \neq p[j]}}, ]

where \(\mathbf{1}_{\{\cdot\}}\) is the indicator function. Your answer is the minimum \(d_i\) over all valid indices i. If the pattern p is longer than the string s, it is impossible to form such a substring, and your program should output -1.

inputFormat

The input consists of two lines:

• The first line contains the string s.
• The second line contains the string p.

Both strings consist of printable characters without spaces.

outputFormat

Output a single integer representing the minimum number of replacement operations required. If p cannot be matched (i.e. if its length is longer than s), output -1.

abcdefg
cde

0