English · Original
Chinese · Translation
Formal · Original
Stepan has a set of _n_ strings. Also, he has a favorite string _s_.
Stepan wants to do the following. He will take some strings of his set and write them down one after another. It is possible that he will take some strings more than once, and will not take some of them at all.
Your task is to determine the minimum number of strings in the set which Stepan needs to take and write so that the string _s_ appears as a subsequence in the resulting written down string.
For example, in the string "_abcd_" strings "_ad_", "_acd_", "_abcd_" appear as subsequences, and strings "_ba_", "_abdc_" don't appear as subsequences.
## Input
The first line contains the integer _n_ (1 ≤ _n_ ≤ 50) — the number of strings in Stepan's set.
The next _n_ lines contain _n_ non-empty strings consisting of lowercase letters of the English alphabet. The length of each of these strings does not exceed 50 symbols. It is possible that some strings from Stepan's set are the same.
The next line contains the non-empty string _s_, consisting of lowercase letters of the English alphabet — Stepan's favorite string. The length of this string doesn't exceed 2500 symbols.
## Output
Print the minimum number of strings which Stepan should take from the set and write them down one after another so that the string _s_ appears as a subsequence in the resulting written down string. Each string from the set should be counted as many times as Stepan takes it from the set.
If the answer doesn't exsist, print _\-1_.
[samples]
## Note
In the first test, Stepan can take, for example, the third and the second strings from the set, write them down, and get exactly his favorite string.
In the second example Stepan can take, for example, the second, the third and again the second strings from the set and write them down. Then he will get a string "_aabaaaab_", in which his favorite string "_baaab_" is a subsequence.
In the third test Stepan can not get his favorite string, because it contains the letter "_c_", which is not presented in any of the strings in the set.
Stepan 有一个包含 #cf_span[n] 个字符串的集合。此外，他有一个最喜欢的字符串 #cf_span[s]。
Stepan 想要进行如下操作：他将从集合中取出一些字符串，并将它们按顺序写下来。他可以多次取同一个字符串，也可以不取某些字符串。
你的任务是确定 Stepan 需要取出并写下的最少字符串数量，使得字符串 #cf_span[s] 作为子序列出现在最终写下的字符串中。
例如，在字符串 "_abcd_" 中，字符串 "_ad_"、"_acd_"、"_abcd_" 都作为子序列出现，而字符串 "_ba_"、"_abdc_" 则不是子序列。
第一行包含整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 50]）—— Stepan 集合中字符串的数量。
接下来的 #cf_span[n] 行包含 #cf_span[n] 个非空字符串，均由英文小写字母组成。每个字符串的长度不超过 #cf_span[50] 个字符。Steppan 的集合中可能存在相同的字符串。
下一行包含一个非空字符串 #cf_span[s]，由英文小写字母组成——Stepan 最喜欢的字符串。该字符串的长度不超过 #cf_span[2500] 个字符。
请输出 Stepan 需要从集合中取出并按顺序写下的最少字符串数量，使得字符串 #cf_span[s] 作为子序列出现在最终写下的字符串中。集合中的每个字符串应根据 Stepan 取用的次数被重复计数。
如果无解，请输出 _-1_。
在第一个测试用例中，Stepan 可以取集合中的第三个和第二个字符串，将它们写下来，恰好得到他最喜欢的那个字符串。
在第二个示例中，Stepan 可以取集合中的第二个、第三个字符串，再取一次第二个字符串，写下来，得到字符串 "_aabaaaab_"，其中他最喜欢字符串 "_baaab_" 是一个子序列。
在第三个测试用例中，Stepan 无法得到他最喜欢字符串，因为它包含字母 "_c_"，而集合中的任何字符串都不包含该字母。
## Input
第一行包含整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 50]）—— Stepan 集合中字符串的数量。接下来的 #cf_span[n] 行包含 #cf_span[n] 个非空字符串，均由英文小写字母组成。每个字符串的长度不超过 #cf_span[50] 个字符。Steppan 的集合中可能存在相同的字符串。下一行包含一个非空字符串 #cf_span[s]，由英文小写字母组成——Stepan 最喜欢的字符串。该字符串的长度不超过 #cf_span[2500] 个字符。
## Output
请输出 Stepan 需要从集合中取出并按顺序写下的最少字符串数量，使得字符串 #cf_span[s] 作为子序列出现在最终写下的字符串中。集合中的每个字符串应根据 Stepan 取用的次数被重复计数。如果无解，请输出 _-1_。
[samples]
## Note
在第一个测试用例中，Stepan 可以取集合中的第三个和第二个字符串，将它们写下来，恰好得到他最喜欢的那个字符串。在第二个示例中，Stepan 可以取集合中的第二个、第三个字符串，再取一次第二个字符串，写下来，得到字符串 "_aabaaaab_"，其中他最喜欢字符串 "_baaab_" 是一个子序列。在第三个测试用例中，Stepan 无法得到他最喜欢字符串，因为它包含字母 "_c_"，而集合中的任何字符串都不包含该字母。
**Definitions:**
- Let $ S = \{s_1, s_2, \dots, s_n\} $ be a multiset of $ n $ non-empty strings over the alphabet $ \Sigma $ (lowercase English letters).
- Let $ t $ be the target string (Stepan’s favorite string), with $ |t| \leq 2500 $.
- A string $ x $ is a *subsequence* of string $ y $ if $ x $ can be obtained by deleting zero or more characters from $ y $ without changing the order of remaining characters.
- We are allowed to select strings from $ S $ with repetition, concatenate them in order, and seek the minimum number of selections such that $ t $ is a subsequence of the concatenation.
**Constraints:**
- $ 1 \leq n \leq 50 $
- Each string in $ S $ has length $ \leq 50 $
- $ |t| \leq 2500 $
- All strings consist of lowercase English letters.
**Objective:**
Find the minimum integer $ k \geq 0 $ such that there exist indices $ i_1, i_2, \dots, i_k \in \{1, 2, \dots, n\} $ (with repetition allowed) for which $ t $ is a subsequence of $ s_{i_1} s_{i_2} \cdots s_{i_k} $.
If no such $ k $ exists, return $ -1 $.
**Precondition for impossibility:**
Let $ \Sigma_t \subseteq \Sigma $ be the set of distinct characters in $ t $.
Let $ \Sigma_S = \bigcup_{s \in S} \text{set of characters in } s $.
If $ \Sigma_t \not\subseteq \Sigma_S $, then return $ -1 $.
**Formal Problem Statement:**
Given:
- A multiset $ S = \{s_1, \dots, s_n\} $ of strings over $ \Sigma $
- A target string $ t \in \Sigma^* $
Find:
$$
\min \left\{ k \in \mathbb{N}_0 \mid \exists (i_1, \dots, i_k) \in [n]^k : t \text{ is a subsequence of } s_{i_1} s_{i_2} \cdots s_{i_k} \right\}
$$
If no such $ k $ exists, output $ -1 $.
API Response (JSON)
{
"problem": {
"name": "I. Composing Of String",
"description": {
"content": "Stepan has a set of _n_ strings. Also, he has a favorite string _s_. Stepan wants to do the following. He will take some strings of his set and write them down one after another. It is possible that ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF795I"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Stepan has a set of _n_ strings. Also, he has a favorite string _s_.\n\nStepan wants to do the following. He will take some strings of his set and write them down one after another. It is possible that ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Stepan 有一个包含 #cf_span[n] 个字符串的集合。此外，他有一个最喜欢的字符串 #cf_span[s]。\n\nStepan 想要进行如下操作：他将从集合中取出一些字符串，并将它们按顺序写下来。他可以多次取同一个字符串，也可以不取某些字符串。\n\n你的任务是确定 Stepan 需要取出并写下的最少字符串数量，使得字符串 #cf_span[s] 作为子序列出现在最终写下的字符串中。\n\n例如...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions:**\n\n- Let $ S = \\{s_1, s_2, \\dots, s_n\\} $ be a multiset of $ n $ non-empty strings over the alphabet $ \\Sigma $ (lowercase English letters).\n- Let $ t $ be the target string (Stepan’s f...",
"is_translate": false,
"language": "Formal"
}
]
}