A collage
Pieces, runs of consecutive characters, are cut out of a text and a phrase is pasted together from them. A piece can be taken from any place in the text, and the same piece as many times as you like. For each phrase find the smallest number of pieces it can be pasted from, or say that it cannot be pasted at all: it contains a character the text lacks. Characters are compared exactly; a space is a character too.
In the third test the text is Eugene Onegin and the phrases are sentences of War and Peace, both in the Russian original; in the fourth it is the other way round: the beginning of War and Peace and lines of Onegin. The texts are brought to one form: lowercase letters, е instead of ё, one kind of dash and quotes, a space instead of a line break.
Input
The first line holds the text, from 1 to 2 · 10⁵ characters long. The second holds the number of phrases q. Then q lines of phrases, each with at least one character, at most 2 · 10⁵ characters in all phrases together. The text and the phrases are in UTF-8, with no spaces at the start or end; lengths are counted in characters, not bytes.
Output
For each phrase on a separate line, the smallest number of pieces or -1.
Examples
Example 1
колокол 4 око локо кол около клок
1 1 -1 2
Example 2
abracadabra 4 cadabra barbara abba cab
1 6 3 2
Limits
- Time · Python
- 5000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Suppose the phrase begins with a piece of length 5, and a piece of length 7 from the same place is also in the text. Could the short one turn out better?
2Hint 2
Greedily taking the longest piece is correct. What remains is to find out quickly how many characters a piece can be extended by. You need a structure that, for each next letter, answers in one step whether the text has such a continuation.
3The idea
The greedy collage is no longer than any other: that is the theorem from the article. Greedy cuts never fall behind the cuts of another collage, because the tail of a piece that is in the text is also in the text. And “is there a continuation” is answered by the suffix automaton of the text: from the root you can walk exactly along the substrings.
4Walkthrough
Build the automaton of the text letter by letter. Read the phrase from the start: follow transitions while they exist, and what was walked is the longest piece. If not a single step could be made, the text has no such character, and the answer is -1. Otherwise count the piece and start again from the root at the same position of the phrase. In Python the transitions are dictionaries; in Go, edge lists in shared arrays are handier: most states have one or two transitions.
4+Solution
5Complexity
Construction is O(n) for a text of length n, with fewer than 2n states. Each phrase is one pass, O(m) for length m: each character of the phrase is read once.
6Common mistakes
- Searching for the piece in the text anew. This is
wrong.py: extend the piece letter by letter and checkpiece in text. The answers are correct, but each check scans the text, and a piece of length L costs L · n. In the sixth test the phrases are made of random letters a and b, a piece is 18 characters on average, and there are about two hundred thousand checks, each over a text of 2 · 10⁵ characters; in the seventh a piece averages 1770 characters. - Cutting at words. A piece can begin and end in the middle of a word: «все с|частливые» is shorter that way.
- Not starting from the root after a failure. Falling back along the suffix link is needed for finding common substrings, but here a piece of the phrase must begin exactly where the previous one ended.
- Bytes instead of characters. The text is in UTF-8: in Go the string has to be split into runes, otherwise a Cyrillic letter becomes two “characters”, and a piece could be cut in the middle of a letter.