# Problem Link:

# Difficulty:

Easy-Medium

# Pre-requisites:

Aho-Corasick, DP

# Explanation:

In order to pass the first sub task it’s sufficient to implement exponential-time brute force solution. In order to go further

some knowledge about Aho-Corasick algo will be required. A lot of articles on Aho-Corasick can be found on the net.

Let’s solve the inverse problem first. Consider that you have a set of strings **D** and a string **T** and now it’s required to calculate

the total number of occurences of all the strings from **D** in **S**. This problem is a standard for Aho-Corasick algo. The standard

solution builds a trie from the set of strings **D** with O(total length of all the strings from **D**) nodes. Then, suffix links are calculated and

with the usage of suffix links it’s possible to calculate the number of strings that end in every node of a trie and in every it’s suffix.

The next step is turning a trie in the automaton with O(states*alphabet) transitions. After this, you will have an automaton on which you

can make **N** steps in order to calculate the number of occurences all the required substrings. This is the brief description of the inverse

problem solution. More detailed description can be found in almost any Aho-Corasick tutorial, because this “inverse” problem is actually a

well known one.

Now, how to solve the original problem. There is a DP soltuion. As it was mentioned before, there’ll be O(total length of strings from **D**)

states in the automaton. So it’s possible to have a DP state of the form (number of letters already processed, current position in the automaton).

The transition then is quite straightforward: if the current symbol is a question mark, then you can have 26 possible choices. Otherwise,

the choice is unique - you can not use all the symbols but the current one. This way you can get the maximal number of occurences.

In order to restore the string itself, you can act greedily. You can iterate through the symbols of the string **S**, starting from the first one.

If the current character is a letter, then there’s only one choice. Otherwise, you can iterate through all the possible characters, namely

‘a’ to ‘z’ and choose the transition to the state with the maximal DP value in it (if there are several such transitions, you can choose the

one with the minimal character). It becomes possible if your DP state is (the size of the

current suffix, the position in the automaton), because adding a symbol is just a transition from one suffix to another, smaller one and in

this case, the DP will contain all the necessary information about the remaining part of the string.

# Setter’s Solution:

Can be found here

# Tester’s Solution:

Can be found here