305030: CF955D. Scissors
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Scissors
题意翻译
给定两个串$s$,$t$和整数$k$,你可以在$s$中取出任意的两个不相交的串,将它们按顺序拼在一起形成一个新串。 求一种取串的方案使得$t$是新串的子串。 ps:k为两个长度为k的不相交的子串题目描述
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?输入输出格式
输入格式
The first line contains three integers $ n $ , $ m $ , $ k $ $ (2<=m<=2·k<=n<=5·10^{5}) $ — 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.
输出格式
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.
输入输出样例
输入样例 #1
7 4 3
baabaab
aaaa
输出样例 #1
Yes
1 5
输入样例 #2
6 3 2
cbcbcb
bcc
输出样例 #2
Yes
2 5
输入样例 #3
7 5 3
aabbaaa
aaaaa
输出样例 #3
No