<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

431. Wildcards
Time limit per test: 2.5 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



You are given a list of files in a directory and need to match a specific subset of these files. You've decided to do that with a single string containing wildcards.

More precisely, each file name is a string consisting of lowercase English letters ('a' through 'z'). You want to craft a string consisting of lowercase English letters, asterisks ('*'), and question marks ('?'). An asterisk matches any sequence of letters (including empty). A question mark matches exactly one letter. See examples for further clarification.

Given a list of file names that you want to match and the list of file names that you don't want to match, output a string (which may include wildcards) that will achieve that.

Input
The first line of the input file contains two integers n and m (1 ≤ n, m ≤ 10) — the number of file names to match and the number of file names not to match, respectively. The next n lines contain file names to match, one per line, each no more than 11 characters long, without any whitespace expect newlines. The next m lines contain file names not to match in the same format. All file names in the input file are different.

Output
Output one string that will do the required matches. The length of that string must not exceed 100. If there're several possible solutions, output any. If there's no solution, output "OOPS" (without quotes) instead.

Example(s)
sample input
sample output
2 2
list
tablexx
dataone
datatwo


<|response|>
## 1) Abridged problem statement

You are given:

- `n` file names that must match
- `m` file names that must not match
  (1 ≤ n, m ≤ 10, each name is lowercase, length ≤ 11, all distinct)

Output one pattern string (length ≤ 100) over:

- lowercase letters `a..z`
- `?` matches exactly one letter
- `*` matches any sequence of letters (possibly empty)

The pattern must match all required names and none of the forbidden names. If impossible, print `OOPS`.

---

## 2) Key observations

1. Input sizes are tiny: at most 20 total strings, each length ≤ 11. This allows backtracking / search over candidate patterns.

2. Any valid pattern must match every "good" string; in particular, it must match the shortest good string `base`. Using the shortest string as a "skeleton" greatly reduces the search space.

3. We can construct patterns by walking through `base` and gradually appending:
   - a literal character (match exactly this char)
   - `?` (match any single char)
   - `*c` (skip any number of chars, then match a specific anchor char `c`)

4. For each candidate pattern, we can quickly test it against all strings using a standard wildcard matching algorithm (glob matching with `*` and `?`).

5. Pattern length limit (100) is generous; with `base` length ≤ 11, our constructed patterns stay short.

---

## 3) Full solution approach

**Wildcard matching (`match_classic`, `match_bitwise`, `match`):**

`match_classic` implements greedy glob matching: walk pointers through pattern and text; on `?` consume one char; on literal check for exact match; on `*` remember the star position and expand it if a later mismatch occurs. For length ≤ 11 this is fast.

`match_bitwise` maintains a bitmask where bit `i` represents "the pattern processed so far can match the text prefix of length `i`". It handles `*`, `?`, and literals via bit operations. The wrapper `match()` selects bitwise for name lengths 8..62, classic otherwise.

**Check (`check_all(p)`):** tests `p` against all strings, requiring a match on the first `n` and a non-match on the next `m`.

**Backtracking (`rec(p, suff_to_match)`):**
- `p` is the pattern built so far; `suff_to_match` is the remaining suffix of `base`.
- If `suff_to_match` is empty and `check_all(p)` is true → done.
- If `check_all(p + "*")` is true → return `p + "*"`.
- If suffix is empty but not valid → fail.
- Otherwise, for each position `i` in `suff_to_match`, choose `suff_to_match[i]` as the next anchor: always try `"*"+c`; if `i == 0`, also try the literal `c` and `?`. Recurse with the remaining suffix `suff_to_match[i+1:]`.

If recursion finds nothing, print `OOPS`.

---

## 4) C++ implementation

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

bool match_classic(string pattern, string name) {
    int px = 0;
    int nx = 0;
    int next_px = 0;
    int next_nx = 0;
    while(px < (int)pattern.size() || nx < (int)name.size()) {
        if(px < (int)pattern.size()) {
            char c = pattern[px];
            if(c == '?') {
                if(nx < (int)name.size()) {
                    px++;
                    nx++;
                    continue;
                }
            } else if(c == '*') {
                next_px = px;
                next_nx = nx + 1;
                px++;
                continue;
            } else {
                if(nx < (int)name.size() && name[nx] == c) {
                    px++;
                    nx++;
                    continue;
                }
            }
        }
        if(0 < next_nx && next_nx <= (int)name.size()) {
            px = next_px;
            nx = next_nx;
            continue;
        }
        return false;
    }
    return true;
}

uint64_t char_masks[26];

bool match_bitwise(string pattern, string name) {
    const uint64_t mask_all = (1llu << ((uint64_t)name.size() + 1)) - 1llu;

    memset(char_masks, 0, sizeof(char_masks));
    for(uint64_t i = 0; i < (uint64_t)name.size(); i++) {
        char_masks[name[i] - 'a'] |= (1llu << i);
    }

    uint64_t mask = 1;
    for(char c: pattern) {
        if(c == '*') {
            mask = mask_all - ((mask & -mask) - 1llu);
        } else if(c == '?') {
            mask = (mask << 1llu);
        } else {
            mask = (mask & char_masks[c - 'a']) << 1llu;
        }

        mask = mask & mask_all;
        if(mask == 0) {
            return false;
        }
    }

    return mask & (1llu << (uint64_t)name.size());
}

bool match(string pattern, string name) {
    if(8 <= name.size() && name.size() <= 62) {
        return match_bitwise(pattern, name);
    } else {
        return match_classic(pattern, name);
    }
}

int n, m;
vector<string> a;

void read() {
    cin >> n >> m;
    a.resize(n + m);
    for(int i = 0; i < n + m; i++) {
        cin >> a[i];
    }
}

bool check_all(string p) {
    for(int i = 0; i < n + m; i++) {
        bool should_match = i < n;
        if(match(p, a[i]) != should_match) {
            return false;
        }
    }
    return true;
}

pair<bool, string> rec(string p, string suff_to_match) {
    if(suff_to_match.empty() && check_all(p)) {
        return {true, p};
    } else if(check_all(p + "*")) {
        return {true, p + "*"};
    } else if(suff_to_match.empty()) {
        return {false, ""};
    }

    for(int i = 0; i < (int)suff_to_match.size(); i++) {
        vector<string> options = {"*"};
        options[0].push_back(suff_to_match[i]);

        if(i == 0) {
            options.push_back(string(1, suff_to_match[i]));
            options.push_back("?");
        }

        string new_suff = suff_to_match.substr(i + 1);
        for(string mid: options) {
            auto [ok, ans] = rec(p + mid, new_suff);
            if(ok) {
                return {true, ans};
            }
        }
    }

    return {false, ""};
}

void solve() {
    // Some intuition on how globs / shell matching works is useful for this
    // problem. One good summary is: https://research.swtch.com/glob. The
    // algorithm we are going to use is the one where where we always maintain
    // the position of the last *, and whenever we fail matching, we refresh the
    // position to the last *. This is quadratic in worst case, but for the
    // given inputs works well. The core for our approach is that because all
    // inputs are short (<= 11 characters), it's likely that the answer will
    // also be short. Particularly, we can have at most 11 non-star characters.
    // And after each of them we can either have a star or not have one. There
    // is also no reason for having two stars in a row. Let's fix the shortest
    // string s in the first set. We know we have to match it, so let's try to
    // generate the set of all candidate patterns. One way is to backtrack it by
    // starting with an empty pattern, and incrementally either adding the first
    // available character, a ?, or a *. The issue comes from the fact that we
    // need to track what the "first available character" is when it comes to
    // stars. It's also unclear how to bound the complexity of this approach.
    // One way is to think of it as selecting a subset of L <= |s| characters
    // that will stay as is, then this implies that the rest of the |s| - L will
    // either be covered by a * or a ?. The naive way is that each of the |s| -
    // L characters can either be there or no, and then we have 2^(|s|+1)
    // possible gaps to put the *. This is already less than a few million, but
    // we are actually over-counting because it never makes sense to put two
    // stars in a row. This solution is fast enough to pass, but a nice
    // observation that can theoretically speed this up is to actually do a
    // bitwise wildcard matching algorithm that maintains a mask of prefixes of
    // the text that can be matched, and incrementally adds characters from the
    // pattern. However, in practice the classic greedy matching algorithm is
    // faster for this problem.

    string base = a[0];
    for(int i = 0; i < n; i++) {
        if(base.size() > a[i].size()) {
            base = a[i];
        }
    }

    auto [ok, ans] = rec("", base);
    if(ok) {
        cout << ans << endl;
    } else {
        cout << "OOPS" << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 5) Python implementation

```python
import sys
sys.setrecursionlimit(10**7)


def match_classic(pattern: str, name: str) -> bool:
    px = 0
    nx = 0
    last_star_px = -1
    next_nx_after_star = -1

    while px < len(pattern) or nx < len(name):
        if px < len(pattern):
            c = pattern[px]
            if c == '?':
                if nx < len(name):
                    px += 1
                    nx += 1
                    continue
            elif c == '*':
                last_star_px = px
                next_nx_after_star = nx + 1
                px += 1
                continue
            else:
                if nx < len(name) and name[nx] == c:
                    px += 1
                    nx += 1
                    continue

        if last_star_px != -1 and 0 <= next_nx_after_star <= len(name):
            px = last_star_px
            nx = next_nx_after_star
            next_nx_after_star += 1
            continue

        return False

    return True


def solve() -> None:
    data = sys.stdin.read().strip().split()
    if not data:
        return
    n = int(data[0])
    m = int(data[1])
    a = data[2:2 + n + m]

    base = min(a[:n], key=len)

    def check_all(p: str) -> bool:
        for i, s in enumerate(a):
            should_match = (i < n)
            if match_classic(p, s) != should_match:
                return False
        return True

    def rec(p: str, suff: str):
        if not suff and check_all(p):
            return True, p

        if check_all(p + "*"):
            return True, p + "*"

        if not suff:
            return False, ""

        for i in range(len(suff)):
            c = suff[i]
            new_suff = suff[i + 1:]

            options = ["*" + c]
            if i == 0:
                options.append(c)
                options.append("?")

            for mid in options:
                ok, ans = rec(p + mid, new_suff)
                if ok:
                    return True, ans

        return False, ""

    ok, ans = rec("", base)
    sys.stdout.write((ans if ok else "OOPS") + "\n")


if __name__ == "__main__":
    solve()
```
