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

点击量：196

   这道题是比较基础的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;
}