You are not logged in. Please login at www.codechef.com to post your questions!

×

QMARKS - Editorial

Problem Link:

Practice
Contest

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

asked 24 Nov '13, 14:56

xcwgf666's gravatar image

6★xcwgf666 ♦♦
719436377
accept rate: 0%

edited 16 Jun '15, 11:00

vicky002's gravatar image

1★vicky002 ♦♦
2561314

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×1,722
×12
×10
×3

question asked: 24 Nov '13, 14:56

question was seen: 1,883 times

last updated: 16 Jun '15, 11:00