D. Scissors

Codeforces

IDCF955D

Time1000ms

Memory256MB

Difficulty—

brute forcestrings

English · Original

Chinese · Translation

Formal · Original

Jenya has recently acquired quite a useful tool — _k_\-scissors for cutting strings. They are generally used for cutting out two non-intersecting substrings of length _k_ from an arbitrary string _s_ (its length should be at least 2·_k_ in order to perform this operation) and concatenating them afterwards (preserving the initial order). For example, with the help of 2\-scissors you can cut _ab_ and _de_ out of _abcde_ and concatenate them into _abde_, but not _ab_ and _bc_ since they're intersecting. It's a nice idea to test this tool before using it in practice. After looking through the papers, Jenya came up with two strings _s_ and _t_. His question is whether it is possible to apply his scissors to string _s_ such that the resulting concatenation contains _t_ as a substring? ## Input The first line contains three integers _n_, _m_, _k_ (2 ≤ _m_ ≤ 2·_k_ ≤ _n_ ≤ 5·105) — length of _s_, length of _t_ and the aforementioned scissors' parameter correspondingly. The next two lines feature _s_ and _t_ consisting of lowercase latin letters. ## Output If there is no answer, print «_No_». Otherwise print «_Yes_» and two integers _L_ and _R_ denoting the indexes where cutted substrings start (1\-indexed). If there are several possible answers, output any. [samples] ## Note In the first sample case you can cut out two substrings starting at 1 and 5. The resulting string _baaaab_ contains _aaaa_ as a substring. In the second sample case the resulting string is _bccb_.

Jenya 最近获得了一种非常有用的工具——#cf_span[k]-剪刀，用于切割字符串。这种剪刀通常用于从任意字符串 #cf_span[s]（其长度至少为 #cf_span[2·k] 才能执行此操作）中剪下两个不相交的长度为 #cf_span[k] 的子串，然后将它们拼接起来（保持原始顺序）。例如，使用 #cf_span[2]-剪刀，你可以从 #cf_span[abcde] 中剪下 #cf_span[ab] 和 #cf_span[de]，并将它们拼接为 #cf_span[abde]，但不能剪下 #cf_span[ab] 和 #cf_span[bc]，因为它们相交。在实际使用之前，测试这个工具是个不错的主意。在查阅了论文后，Jenya 找到了两个字符串 #cf_span[s] 和 #cf_span[t]。他的问题是：是否可以对字符串 #cf_span[s] 使用他的剪刀，使得拼接后的结果包含 #cf_span[t] 作为子串？第一行包含三个整数 #cf_span[n], #cf_span[m], #cf_span[k] #cf_span[(2 ≤ m ≤ 2·k ≤ n ≤ 5·105)] —— 分别表示 #cf_span[s] 的长度、#cf_span[t] 的长度以及上述剪刀的参数。接下来两行分别给出由小写拉丁字母组成的字符串 #cf_span[s] 和 #cf_span[t]。如果没有答案，请输出 «_No_»。否则，输出 «_Yes_» 和两个整数 #cf_span[L] 和 #cf_span[R]，表示被剪下的两个子串的起始位置（#cf_span[1]-索引）。如果有多个可能的答案，输出任意一个即可。在第一个样例中，你可以剪下起始位置为 #cf_span[1] 和 #cf_span[5] 的两个子串，得到的字符串 _baaaab_ 包含 _aaaa_ 作为子串。在第二个样例中，得到的字符串是 _bccb_。 ## Input 第一行包含三个整数 #cf_span[n], #cf_span[m], #cf_span[k] #cf_span[(2 ≤ m ≤ 2·k ≤ n ≤ 5·105)] —— 分别表示 #cf_span[s] 的长度、#cf_span[t] 的长度以及上述剪刀的参数。接下来两行分别给出由小写拉丁字母组成的字符串 #cf_span[s] 和 #cf_span[t]。 ## Output 如果没有答案，请输出 «_No_»。否则，输出 «_Yes_» 和两个整数 #cf_span[L] 和 #cf_span[R]，表示被剪下的两个子串的起始位置（#cf_span[1]-索引）。如果有多个可能的答案，输出任意一个即可。 [samples] ## Note 在第一个样例中，你可以剪下起始位置为 #cf_span[1] 和 #cf_span[5] 的两个子串，得到的字符串 _baaaab_ 包含 _aaaa_ 作为子串。在第二个样例中，得到的字符串是 _bccb_。

Let $ s $ be a string of length $ n $, $ t $ a string of length $ m $, and $ k $ a positive integer such that $ 2 \leq m \leq 2k \leq n \leq 5 \cdot 10^5 $. Define two non-overlapping substrings of $ s $ of length $ k $: - $ s_1 = s[L:L+k-1] $, starting at index $ L $ (1-indexed), - $ s_2 = s[R:R+k-1] $, starting at index $ R $ (1-indexed), such that $ L + k - 1 < R $ (i.e., the two substrings do not intersect). Let $ s' = s_1 + s_2 $ be the concatenation of these two substrings. **Objective:** Determine whether there exist indices $ L, R $ with $ 1 \leq L < R \leq n - k + 1 $ and $ L + k \leq R $, such that $ t $ is a substring of $ s' $. If such $ L, R $ exist, output: ``` Yes L R ``` Otherwise, output: ``` No ```

Samples

Input #1

7 4 3
baabaab
aaaa

Output #1

Yes
1 5

Input #2

6 3 2
cbcbcb
bcc

Output #2

Yes
2 5

Input #3

7 5 3
aabbaaa
aaaaa

Output #3

No

API Response (JSON)

{
  "problem": {
    "name": "D. Scissors",
    "description": {
      "content": "Jenya has recently acquired quite a useful tool — _k_\\-scissors for cutting strings. They are generally used for cutting out two non-intersecting substrings of length _k_ from an arbitrary string _s_ ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF955D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Jenya has recently acquired quite a useful tool — _k_\\-scissors for cutting strings. They are generally used for cutting out two non-intersecting substrings of length _k_ from an arbitrary string _s_ ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Jenya 最近获得了一种非常有用的工具——#cf_span[k]-剪刀，用于切割字符串。这种剪刀通常用于从任意字符串 #cf_span[s]（其长度至少为 #cf_span[2·k] 才能执行此操作）中剪下两个不相交的长度为 #cf_span[k] 的子串，然后将它们拼接起来（保持原始顺序）。例如，使用 #cf_span[2]-剪刀，你可以从 #cf_span[abcde] 中剪下 #cf_sp...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ s $ be a string of length $ n $, $ t $ a string of length $ m $, and $ k $ a positive integer such that $ 2 \\leq m \\leq 2k \\leq n \\leq 5 \\cdot 10^5 $.\n\nDefine two non-overlapping substrings of $...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments