Description

Users naturally want to use as few "@" as possible. You are given a wildcard pattern that may contain "?" and "" and a target string. First, determine whether the pattern matches the target string. If it matches, replace every "?" and "" in the original pattern with "@" so that the modified pattern still matches the target string, and find the minimum number of "@" required. All "@" in the modified pattern must represent the same fixed number of characters.

Input Format

The first line contains a string, the wildcard pattern.

The second line contains a string, the original target string.

Output Format

Output a single string on the first line: if the pattern matches the target, output "matched", and on the next line output an integer giving the minimum number of "@" required. If the pattern does not match the target, output "not matched".

1*456??
111111145678

matched
4

1*456
1111111452

not matched

Hint

Sample Explanation 1: The two strings clearly match. The wildcard pattern 1*456?? can be replaced by 1@@@456@, requiring 4 "@" in total, where each "@" replaces two characters. This can be proven optimal.

The wildcard pattern 1*456?? can also be replaced by 1@@@@@@456@@, where each "@" replaces one character, requiring 8 "@", which is not better than the previous case.

Sample Explanation 2: The two strings do not match.

Constraints:

• For 100% of the testdata, the length of each string is less than 3000.
• The original string contains only letters and digits. The wildcard pattern contains only letters, digits, and the wildcards "?" and "*". The matching, if it exists, is unique.

Translated by ChatGPT 5