{"problem":{"name":"E. Liar","description":{"content":"The first semester ended. You know, after the end of the first semester the holidays begin. On holidays Noora decided to return to Vičkopolis. As a modest souvenir for Leha, she brought a sausage of l","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF822E"},"statements":[{"statement_type":"Markdown","content":"The first semester ended. You know, after the end of the first semester the holidays begin. On holidays Noora decided to return to Vičkopolis. As a modest souvenir for Leha, she brought a sausage of length _m_ from Pavlopolis. Everyone knows that any sausage can be represented as a string of lowercase English letters, the length of which is equal to the length of the sausage.\n\nLeha was very pleased with the gift and immediately ate the sausage. But then he realized that it was a quite tactless act, because the sausage was a souvenir! So the hacker immediately went to the butcher shop. Unfortunately, there was only another sausage of length _n_ in the shop. However Leha was not upset and bought this sausage. After coming home, he decided to cut the purchased sausage into several pieces and number the pieces starting from 1 from left to right. Then he wants to select several pieces and glue them together so that the obtained sausage is equal to the sausage that Noora gave. But the hacker can glue two pieces together only when the number of the left piece is less than the number of the right piece. Besides he knows that if he glues more than _x_ pieces, Noora will notice that he has falsified souvenir sausage and will be very upset. Of course Leha doesn’t want to upset the girl. The hacker asks you to find out whether he is able to cut the sausage he bought, and then glue some of the pieces so that Noora doesn't notice anything.\n\nFormally, you are given two strings _s_ and _t_. The length of the string _s_ is _n_, the length of the string _t_ is _m_. It is required to select several pairwise non-intersecting substrings from _s_, so that their concatenation in the same order as these substrings appear in _s_, is equal to the string _t_. Denote by _f_(_s_, _t_) the minimal number of substrings to be chosen so that their concatenation is equal to the string _t_. If it is impossible to choose such substrings, then _f_(_s_, _t_) = ∞. Leha really wants to know whether it’s true that _f_(_s_, _t_) ≤ _x_.\n\n## Input\n\nThe first line contains single integer _n_ (1 ≤ _n_ ≤ 105) — length of sausage bought by Leha, i.e. the length of the string _s_.\n\nThe second line contains string _s_ of the length _n_ consisting of lowercase English letters.\n\nThe third line contains single integer _m_ (1 ≤ _m_ ≤ _n_) — length of sausage bought by Noora, i.e. the length of the string _t_.\n\nThe fourth line contains string _t_ of the length _m_ consisting of lowercase English letters.\n\nThe fifth line contains single integer _x_ (1 ≤ _x_ ≤ 30) — the maximum number of pieces of sausage that Leha can glue so that Noora doesn’t notice anything.\n\n## Output\n\nIn the only line print \"_YES_\" (without quotes), if Leha is able to succeed in creating new sausage so that Noora doesn't notice anything. Otherwise print \"_NO_\" (without quotes).\n\n[samples]\n\n## Note\n\nLet's consider the first sample.\n\nIn the optimal answer, Leha should cut the sausage he bought in the following way: _hloyaygrt = h + loy + a + y + g + rt_. Then he numbers received parts from 1 to 6:\n\n*   _h_ — number 1\n*   _loy_ — number 2\n*   _a_ — number 3\n*   _y_ — number 4\n*   _g_ — number 5\n*   _rt_ — number 6\n\nHereupon the hacker should glue the parts with numbers 2, 4 and 6 and get sausage _loyygrt_ equal to one that is given by Noora. Thus, he will have to glue three pieces. Since _x_ = 3 you should print \"_YES_\" (without quotes).\n\nIn the second sample both sausages coincide with sausages from the first sample. However since _x_ = 2 you should print \"_NO_\" (without quotes).","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"第一学期结束了。你知道，第一学期结束后就是假期。假期里，Noora 决定回到 Vičkopolis。作为给 Leha 的一份谦逊的纪念品，她从 Pavlopolis 带来了一根长度为 $m$ 的香肠。众所周知，任何香肠都可以表示为一个由小写英文字母组成的字符串，其长度等于香肠的长度。\n\nLeha 对这份礼物非常高兴，立即吃掉了香肠。但随后他意识到这是一个相当不妥的行为，因为这根香肠是纪念品！于是这位黑客立刻前往肉铺。不幸的是，店里只有一根长度为 $n$ 的香肠。然而 Leha 并未沮丧，买下了这根香肠。回到家后，他决定将买来的香肠切成若干段，并从左到右将这些段编号为 $1$ 开始。接着他想选出若干段，将它们粘合在一起，使得得到的香肠与 Noora 给他的那根完全相同。但黑客只能将编号较小的段粘合到编号较大的段上。此外，他知道如果粘合超过 $x$ 段，Noora 就会察觉到他伪造了纪念品香肠并会非常生气。当然，Leha 不想让女孩生气。黑客请你帮他判断：他是否能将买来的香肠切开，然后粘合其中若干段，使得 Noora 丝毫察觉不到异常。\n\n形式化地，给你两个字符串 $s$ 和 $t$。字符串 $s$ 的长度为 $n$，字符串 $t$ 的长度为 $m$。你需要从 $s$ 中选出若干互不相交的子串，使得这些子串按其在 $s$ 中出现的顺序连接后，等于字符串 $t$。记 $f(s, t)$ 为使连接结果等于 $t$ 所需选择的最小子串数量。如果不可能选出这样的子串，则 $f(s, t) = ∞$。Leha 真正想知道的是：是否满足 $f(s, t) ≤ x$？\n\n第一行包含一个整数 $n$ ($1 ≤ n ≤ 10^5$) —— Leha 买的香肠长度，即字符串 $s$ 的长度。\n\n第二行包含长度为 $n$ 的字符串 $s$，由小写英文字母组成。\n\n第三行包含一个整数 $m$ ($1 ≤ m ≤ n$) —— Noora 买的香肠长度，即字符串 $t$ 的长度。\n\n第四行包含长度为 $m$ 的字符串 $t$，由小写英文字母组成。\n\n第五行包含一个整数 $x$ ($1 ≤ x ≤ 30$) —— Leha 可以粘合的最大段数，以确保 Noora 不会察觉。\n\n仅在一行中输出 \"_YES_\"（不含引号），如果 Leha 能成功制造出一根 Noora 察觉不到异常的新香肠；否则输出 \"_NO_\"（不含引号）。\n\n考虑第一个样例。\n\n在最优方案中，Leha 应该将他买的香肠切成如下方式：_hloyaygrt = h + loy + a + y + g + rt_。然后他将得到的段从 $1$ 到 $6$ 编号：\n\n此时，黑客应粘合编号为 $2$、$4$ 和 $6$ 的段，得到香肠 _loyygrt_，与 Noora 给他的完全一致。因此他需要粘合三段。由于 $x = 3$，你应该输出 \"_YES_\"（不含引号）。\n\n在第二个样例中，两根香肠与第一个样例中的相同。但由于 $x = 2$，你应该输出 \"_NO_\"（不含引号）。\n\n## Input\n\n第一行包含一个整数 $n$ ($1 ≤ n ≤ 10^5$) —— Leha 买的香肠长度，即字符串 $s$ 的长度。第二行包含长度为 $n$ 的字符串 $s$，由小写英文字母组成。第三行包含一个整数 $m$ ($1 ≤ m ≤ n$) —— Noora 买的香肠长度，即字符串 $t$ 的长度。第四行包含长度为 $m$ 的字符串 $t$，由小写英文字母组成。第五行包含一个整数 $x$ ($1 ≤ x ≤ 30$) —— Leha 可以粘合的最大段数，以确保 Noora 不会察觉。\n\n## Output\n\n仅在一行中输出 \"_YES_\"（不含引号），如果 Leha 能成功制造出一根 Noora 察觉不到异常的新香肠；否则输出 \"_NO_\"（不含引号）。\n\n[samples]\n\n## Note\n\n考虑第一个样例。\n\n在最优方案中，Leha 应该将他买的香肠切成如下方式：_hloyaygrt = h + loy + a + y + g + rt_。然后他将得到的段从 $1$ 到 $6$ 编号：\n\n_h_ —— 编号 $1$\n_loy_ —— 编号 $2$\n_a_ —— 编号 $3$\n_y_ —— 编号 $4$\n_g_ —— 编号 $5$\n_rt_ —— 编号 $6$\n\n此时，黑客应粘合编号为 $2$、$4$ 和 $6$ 的段，得到香肠 _loyygrt_，与 Noora 给他的完全一致。因此他需要粘合三段。由于 $x = 3$，你应该输出 \"_YES_\"（不含引号）。\n\n在第二个样例中，两根香肠与第一个样例中的相同。但由于 $x = 2$，你应该输出 \"_NO_\"（不含引号）。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ s \\in \\Sigma^n $ and $ t \\in \\Sigma^m $ be strings over the alphabet $ \\Sigma $ of lowercase English letters, with $ n \\geq m $.  \nLet $ x \\in \\mathbb{Z}^+ $ be the maximum allowed number of substrings.\n\nLet $ f(s, t) $ denote the minimal number of pairwise non-intersecting, contiguous, non-overlapping substrings of $ s $, taken in left-to-right order, whose concatenation equals $ t $. If no such decomposition exists, $ f(s, t) = \\infty $.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ 1 \\leq m \\leq n $  \n3. $ 1 \\leq x \\leq 30 $\n\n**Objective**  \nDetermine whether $ f(s, t) \\leq x $.  \nOutput \"YES\" if true, \"NO\" otherwise.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF822E","tags":["binary search","dp","hashing","string suffix structures"],"sample_group":[["9\nhloyaygrt\n6\nloyyrt\n3","YES"],["9\nhloyaygrt\n6\nloyyrt\n2","NO"]],"created_at":"2026-03-03 11:00:39"}}