This page is still under construction.

Parts of this page are still being built. What you see may change.

Dictionary of Obscene Words

Time limit1sMemory limit128 MB

Summary
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 S1,S2,…,SnS_1, S_2, \ldots, S_n and a text TT. Determine whether TT contains at least one of the dictionary words as a subsequence. If it does, find the length of the shortest prefix of TT that already contains such a subsequence.

Input

The first line contains a single integer nn, the number of words in the dictionary. Each of the next nn lines contains one dictionary word. Every word consists of ASCII characters whose codes lie between 3232 and 127127, inclusive (so a word may contain spaces). The following line contains the text TT, made up of the same set of characters. The total length of all dictionary words does not exceed 100100 KiB (100×210100 \times 2^{10} bytes). The total size of the input does not exceed 11 MiB (2202^{20} bytes).

Output

Print NO if the text contains no obscene word as a subsequence. Otherwise print YES X, where XX is the length of the shortest prefix of TT that contains some obscene word as a subsequence.

Examples2

  1. Example 1

    Input
    2
    hello
    world
    abracadabra
    
    Expected output
    NO
    
  2. Example 2

    Input
    2
    hello
    world
    zzzheluuuulottt
    
    Expected output
    YES 12