[ 杂题 ] Codeforces955D Scissors

对于 t t 的每个前缀，双指针扫一遍求出在 ss 中出现的最左的位置，对每个后缀求出最右的位置。然后枚举 t t 中分割的位置就好了。

注意判断 tt 在一个子串中出现的情况。

UPD:

感谢 lifelikes 指出错误。

假如要求出最左的位置，由于要保证选的字符串长度至少为 k k ，所以初始时指针在 kk 。

但这样有一种情况，就是 t t 串的一个前缀可以匹配 ss 串以 k k 为右端的一个子串，而此时指针已经移到了后面。一种解决办法是在这种情况出现时将指针移到 kk ，但这样无法保证复杂度。

我们先求出 t t 中所有能匹配 ss 串以 k k 为右端的一个子串的位置，记最左边的位置为 firstfirst ，最右边的位置为 second s e c o n d ，那么在 [first+1,second−1] [ f i r s t + 1 , s e c o n d − 1 ] 中的位置肯定不是最优的，所以分别做 [1,first],[second,m] [ 1 , f i r s t ] , [ s e c o n d , m ] 就好了。

#include<bits/stdc++.h>
using namespace std;
const int N=;
const int H=;
const int P=;
int k,n,m;
int pos;
int f[N],g[N];
int hs[N],ht[N],p[N];
int x,y,lst,fst;
char s[N],t[N];
bool Check(int l,int r,int L,int R) {
    int t=(hs[r]-ll*hs[l-]*p[r-l+])%P;
    t=(t+P)%P;
    int T=(ht[R]-ll*ht[L-]*p[R-L+])%P;
    T=(T+P)%P;
    return t==T;
}
bool Solve() {
    pos=;
    for(int i=;i<=m;i++) {
        while(pos<i) ++pos;
        while(pos<=n) {
            if(Check(pos-i+,pos,,i)) break;
            ++pos;
        }
    }
    if(max(pos,k)+k<=n) {
        printf("Yes\n%d %d\n",max(,pos-k+),max(pos,k)+);
        return ;
    }
    pos=n;
    for(int i=m;i;i--) {
        while(pos+m-i>n) --pos;
        while(pos) {
            if(Check(pos,pos+m-i,i,m)) break;
            --pos;
        }
    }
    if(n-max(n-pos+,k)-k>) {
        printf("Yes\n%d %d\n",n-max(n-pos+,k)-k,n-max(n-pos+,k)+);
        return ;
    }
    return ;
}
void Solve1(int l,int r) {
    int pos=k;
    for(int i=l;i<=r;i++) {
        while(pos<i) ++pos;
        while(pos<=n) {
            if(Check(pos-i+,pos,,i)) break;
            ++pos;
        }
        f[i]=pos<=n?pos:;
    }
}
void Solve2(int l,int r) {
    int pos=n-k+;
    for(int i=r;i>=l;i--) {
        while(pos+m-i>n) --pos;
        while(pos) {
            if(Check(pos,pos+m-i,i,m)) break;
            --pos;
        }
        g[i]=pos;
    }
}
int main() {
    scanf("%d%d%d",&n,&m,&k);
    scanf("%s%s",s+,t+);
    p[]=;
    for(int i=;i<=n;i++) p[i]=ll*p[i-]*H%P;
    for(int i=;i<=n;i++) hs[i]=(ll*hs[i-]*H+s[i]-'a')%P;
    for(int i=;i<=m;i++) ht[i]=(ll*ht[i-]*H+t[i]-'a')%P;
    if(m<=k&&Solve()) return ;
    lst=fst=;
    for(int i=;i<=m&&i<=k;i++)
        if(Check(k-i+,k,,i)) {
            lst=i;
            if(fst!=) fst=i;
            f[i]=k;
        }
    Solve1(,fst-);Solve1(lst+,min(m,k));
    lst=fst=m;
    for(int i=m;i&&i>=m-k+;i--)
        if(Check(n-k+,n-k++m-i,i,m)) {
            lst=i;
            if(fst!=m) fst=i;
            g[i]=n-k+;
        }
    Solve2(fst+,m);Solve2(max(,m-k+),lst-);
    for(int i=;i<m;i++) 
        if(f[i]&&g[i+]&&f[i]<g[i+]) {
            x=f[i]-k+;y=g[i+];
            break;
        }
    if(x) printf("Yes\n%d %d\n",x,y);else puts("No");
    return ;
}