I suggest choosing some small $k$ (e.g., $k=3$) and breaking up each wildcard-free substring within each pattern into all overlapping $k$-mers: e.g. the pattern
abcd*ef?ghij would give you the 3-mers
hij. Any string that matches
abcd*ef?ghij must contain all these 3-mers, so we could pick one of them (say,
ghi) at preprocessing time; later, when we have a string that we want to test, we know that we only need to do a "full check" for the pattern
abcd*ef?ghij if the string contains the 3-mer
ghi. So the idea is to build, at preprocessing time, an index $z$ that can, for any given $k$-mer $x$, quickly report all the patterns that we need to run a full check on if $x$ is present anywhere in the string. For speed, this $z$ can take the form of a large in-memory array whose index is the $k$-mer, encoded as an integer: this means that, for an alphabet of size $A$, it will have $A^k$ entries, each containing a list of pattern IDs. For speed reasons (see below) you may want to round the alphabet size up to the next power of 2 (so, e.g., if the alphabet is lowercase letters, you could round up to an alphabet size of 32, and comfortably get $k=5$).
- For each pattern $p_i$:
- Choose any wildcard-free $k$-mer $x$ in $p$; the "least likely" $k$-mer is the best choice.
- Add $i$ to the list $z[x]$.
- For each $k$-mer $x$ in the given string $s$:
- For each $i$ in $z[x]$:
- Check whether $p_i$ matches $s$ "the hard way".
- If there are any patterns that have no wildcard-free $k$-mer, test each of them against $s$ "the hard way".
Because each pattern appears at most once anywhere in the index $z$, this will never test a pattern twice, so the only overhead over the naive algorithm is the cost of breaking the string into $k$-mers. For alphabets with power-of-2 sizes, this can be done in linear time with bit shifts and bitwise OR operations.
Generally, a higher $k$ is better, but requires exponentially more memory -- and also means that patterns have to have longer wildcard-free substrings in order to benefit from the index. You'll need to experiment.