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