Task 5 - Pattern
 

Wildcard Patterns

PROBLEM

Wildcard patterns are frequently used to specify sets of names. For example, we can specify all file names which start with h and end with bak by the pattern h*bak.

A wildcard pattern is a string that may contain * characters as wildcards. A string W matches a pattern P if W can be obtained from P by substituting some (possibly empty) string for each * character in P. (Different strings may be substituted for different occurrences of *.) For a pair of patterns P1 and P2, Q is a common pattern of P1 and P2 if any string that matches Q also matches both P1 and P2.

A set Q1, Q2, …, QL of common patterns is called complete if any string that matches both P1 and P2 matches at least one Qi (1<=i<=L).

You are to write a program that for a given pair of patterns P1 and P2 computes

  1. at least one common pattern (but no wrong patterns); or
  2. a complete set of common patterns with no more than 6666 entry; or
  3. a complete set of common patterns which is minimal in the number of elements (i.e. there is no smaller set of common patterns, which is complete) Note that solving this task you will earn 100% plus an additional 50% of the scores.

INPUT

The first and the second lines of the file pattern.in contain the patterns P1 and P2. The patterns are composed of the lowercase letters from ‘a’ to ‘z’ and the ‘*’ character. Each pattern contains no more than 20 characters. The number of the * characters in each pattern is between 0 and 6.

OUTPUT

The first line of the file pattern.out must contain the integer K, the number of common patterns computed as a solution. The next K lines contain one common pattern in each line; these constitute the solution.

The order of the common patterns is irrelevant. Both case B and C can be solved within the specified limit of 6666 entries. If there is no common pattern of P1 and P2, then the first and only line must contain the number 0.

EXAMPLE INPUT AND OUTPUT

pattern.in

pattern.out for case C

*ab*

4

ba*b

ba*ab*b
 

bab*b
 

ba*ab
 

bab

GRADING

If your solution solves case A then you obtain 5 points. If your solution solves case B then you obtain 10 points. If your solution solves case C then you obtain 15 points.