# CF955D Scissors 题解【KMP】【字符串】【贪心】

这道题是比较基础的KMP+特判问题。

## Description

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\cdot 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\le m\le 2\cdot k\le n\le 5\cdot 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.

## 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.

## Examples

input
7 4 3
baabaab
aaaa
output
Yes
1 5
input
6 3 2
cbcbcb
bcc
output
Yes
2 5
input
7 5 3
aabbaaa
aaaaa
output
No

## 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$.

## 题意：

给出一个串$S$，要求在$S$中找到两个不相交的子串$p_1,p_2,|p_1|,|p_2|=k$，使得给定的$T$是$p_1+p_2$的子串。有解输出Yes和两个子串的位置，无解输出No。

## 题解：

这个题其实考了KMP，主要思路是在KMP中把模式串，也就是$T$的前后缀尽可能地组合出来，而且要使得分别是长度为$k$的串的前后缀，因此要考虑前后补全的问题。

合法情况下，$p_1$的后断点和$p_2$的前断点需要在$[k,n-k]$的范围内，同时$x_1<x_2$。特殊情况是KMP全部匹配，根据数据范围，此时一定能构造出答案。

那么我们只需要在KMP的时候多写几步，如果断点超过了$k$，那么沿着它的$nxt$的位置就都能按照这个断点来算，因为要尽可能组合前后缀，那么前缀要尽量靠前，如果已经被赋过值的就贪心地不给它赋了。同时再reverse过来再做一遍后缀即可。直接多开一个数组存模式串对应主串中第一次出现大于等于$k$的位置就可以完成。

然后枚举可能的断点进行匹配就可以了，如果不能匹配，说明无解，输出No。

## Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::reverse;
char s[500500],t[500500];
int nxt[500500],f1[500500],f2[500500];
int main()
{
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
scanf("%s",s+1);
scanf("%s",t+1);
for(int j=0,i=2;i<=m;++i)//第一次匹配的求nxt
{
while(j&&t[i]!=t[j+1])
j=nxt[j];
if(t[i]==t[j+1])
++j;
nxt[i]=j;
}
for(int j=0,i=1;i<=n;++i)
{
while(j&&s[i]!=t[j+1]||j==m)
j=nxt[j];
if(s[i]==t[j+1])
++j;
if(j==m)//说明完全匹配，直接构造方案
{
puts("Yes");
int ans=i-m+1;
if(i+k>n)
ans=n-2*k+1;
printf("%d %d\n",ans,ans+k);
return 0;
}
if(i>=k&&!f1[j])
{
f1[j]=i;
int p=nxt[j];
while(p&&!f1[p])
{
f1[p]=i;
if(!p)
break;
p=nxt[p];
}
}
}
reverse(s+1,s+1+n);
reverse(t+1,t+1+m);
for(int j=0,i=2;i<=m;++i)//第二次匹配的是后缀
{
while(j&&t[i]!=t[j+1])
j=nxt[j];
if(t[i]==t[j+1])
++j;
nxt[i]=j;
}
for(int j=0,i=1;i<=n;++i)
{
while(j&&s[i]!=t[j+1]||j==m)
j=nxt[j];
if(s[i]==t[j+1])
++j;
if(i>=k&&!f2[j])
{
f2[j]=n-i+1;
int p=nxt[j];
while(p&&!f2[p])
{
f2[p]=n-i+1;
if(!p)
break;
p=nxt[p];
}
}
}
for(int i=std::max(1,m-k);i<=k;++i)//枚举，统计答案
if(f1[i]&&f2[m-i]&&f1[i]<f2[m-i])
{
puts("Yes");
printf("%d %d\n",f1[i]-k+1,f2[m-i]);
return 0;
}
puts("No");
return 0;
}

Subscribe

/* */