An archivist is restoring a damaged master tape. The desired restored content is given as a target string of lowercase letters. The archive holds a library of reference tapes; the restoration tool can only cut a splice starting at the very beginning of one reference tape — so every splice must equal some (non-empty) prefix of some reference tape, never a fragment cut from its middle or end — and the same reference tape design may supply any number of splices.
The archivist wants to lay splices end to end, in order, with no gaps and no overlaps, so their concatenation equals the target tape exactly, using as few splices as possible. If the target cannot be reconstructed this way, the archivist needs to know that too.
The first line contains a single integer n, the number of reference tapes. Each of the next n lines contains one reference tape's content. The final line contains the target string. All strings consist only of lowercase English letters.
A single integer: the minimum number of splices needed to reconstruct the target exactly, or -1 if it cannot be reconstructed.
Example 1
Input
2 ab abc abcabc
Expected
2
Explanation
The reference tapes are 'ab' and 'abc'. The whole string 'abc' is itself a prefix of the second reference tape, so the target 'abcabc' can be assembled from exactly two splices, each equal to the full content 'abc'. No single splice can cover more than 3 characters starting from either half, so 2 is optimal.
Example 2
Input
1 a aaa
Expected
3
Explanation
The only reference tape is 'a', whose only non-empty prefix is 'a' itself (length 1). So every splice contributes exactly one character, and covering 'aaa' requires exactly 3 splices.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →