Dictionary of Obscene Words
Time limit1sMemory limit128 MB
Given dictionary words and a text, find the length of the shortest prefix of the text containing some word as a subsequence.
- Level
Medium7 of 10
- Topics
- Dynamic programming, String, Greedy
- Solved
- No attempts yet
Problem
You are given a dictionary of obscene words and a text . Determine whether contains at least one of the dictionary words as a subsequence. If it does, find the length of the shortest prefix of that already contains such a subsequence.
Input
The first line contains a single integer , the number of words in the dictionary. Each of the next lines contains one dictionary word. Every word consists of ASCII characters whose codes lie between and , inclusive (so a word may contain spaces). The following line contains the text , made up of the same set of characters. The total length of all dictionary words does not exceed KiB ( bytes). The total size of the input does not exceed MiB ( bytes).
Output
Print NO if the text contains no obscene word as a subsequence. Otherwise print YES X, where is the length of the shortest prefix of that contains some obscene word as a subsequence.