P2635 String Matching with Wildcards

Wildcards are keyboard characters used to stand in for one or more real characters when we do not know the exact characters or do not want to type the full name. Common wildcards include the question mark (?) and the asterisk (*), where "?" stands for exactly one character and "*" stands for zero or more characters. We further define a wildcard "@", with the rule that within a single string, each "@" stands for the same fixed number of characters.

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.

The first line contains a string, the wildcard pattern. The second line contains a string, the original target string.

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".

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