昨晚CF比赛比较颓，今天有心情写题解就不错了QWQ
洛谷题目页面传送门 & CodeForces题目页面传送门
给定字符串(a,b,|a|=n,|b|=m)，求是否可以在(a)中选(2)个长度为(s)的不相交子串，使得(b)是这(2)个串按在(a)中的顺序连起来后得到的串的子串，若可以，输出任一选法。
(2le mle 2sle nle 5 imes 10^5)。
设从(a)中选出的(2)个子串为(a1,a2)。分(2)种情况：
- (a1)或(a2)完全包含(b)；
- (a1)的一个后缀与(a2)的一个前缀组成(b)。
第(1)种情况比较容易，直接将(b)作为模式串匹配(a)（这里我用的是Z算法（如果聪明的读者还不知道Z算法是什么，please点击这个）），匹配成功的位置再分(2)种情况：(a1)包含(b)和(a2)包含(b)。(a1)包含(b)的情况考虑贪心地将(a1)最左化，好给(a2)留位置，最后如果放得下直接输出答案return 0;；(a2)包含(b)类似。
第(2)种情况，设(lft_i)表示满足(a_{jsim j+s-1})的长度为(i)的后缀匹配(b)的长度为(i)的前缀的最小的(j)，(rit_i)表示满足(a_{jsim j+s-1})的长度为(i)的前缀匹配(b)的长度为(i)的后缀的最大的(j)，若没有满足条件的(j)则分别为(+infty,-infty)。“最小”和“最大”是基于贪心的思想，与第(1)种情况类似，为的是尽可能给另一个子串留位置。这样最后我们可以枚举(iin[0,s])，若(m-iin[0,s])且(lft_i+s-1<rit_{m-i})，则存在答案((lft_i,rit_{m-i}))。
下面考虑(lft)和(rit)数组怎么求。以(lft)为栗例，我们令(c=b+ exttt{!}+a)，对(c)跑一遍Z算法。(forall iin[1,n])，考虑若(a1)的后缀从第(i)位开始，能影响到哪些(lft_j)。显然(j_{max}=z_{c,m+1+j})，因为最多能往后拓展(z_{c,m+1+j})个字符，满足这个后缀与(b)的前缀匹配。(j_{min})呢？(j)越小，即(a1)在第(i)位后面的字符越少，那么(a1)在第(i)位前面的字符就越多，多到一定程度就会抵到位置(1)，所以(j_{min})是刚好抵到的情况，如果不会抵到就是(1)。于是(j_{min}=max(s-(i-1),1))。算出影响范围后，我们要去“影响”啊，即令(
equire{cancel}forall jin[j_{min},j_{max}],lft_j=min(lft_j,i+jcancel{-1}-scancel{+1}))。这个可以用线段树维护，差分也可以，虽然都是(mathrm O(nlog n))，但差分好写一点。
下面讲具体怎么差分：(forall kin[0,m])，维护一个添加序列(add_k)和删除序列(del_k)。对于每次影响，在(add_{j_{min}})和(del_{j_{max}+1})里插入(i-s)。最后维护一个multiset(st)（初始为({+infty})），从(i=1)到(i=m)递推，每次将(add_i)里的元素insert进去，将(del_i)里的元素erase掉（注意如果写st.erase(x)会把所有的(x)都删掉，应该写st.erase(st.find(x))），*st.begin()+i就是(lft_i)。
(rit)数组的求法类似，不同在于(c=b^mathrm r+ exttt!+a^mathrm r)，访问(z)数组时要访问在倒串中的位置，(j_{min}=max(s-(n-i),1),j_{max}=z_{c,m+1+(n+1-i)})，影响为(forall jin[j_{min},j_{max}],rit_j=min(rit_j,i-j+1))，(st)初始为({-infty})，每次插入(i+1)，(rit_i)为*--st.end()-i。
下面贴代码吧：（写不动了）
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int inf=0x3f3f3f3f;
const int N=500000,M=500000;
int n/*|a|*/,m/*|b|*/,s/*要选的字串的长度*/,t/*|c|*/;
int rev_pos(int pos){return n+1-pos;}//在倒串中的位置
char a[N+5],b[M+5],ra[N+5]/*rev(a)*/,rb[M+5]/*rev(b)*/,c[N+1+M+5]/*b+'!'+a或rb+'!'+ra*/;
void con(char str1[],char str2[]){//令c=str1+'!'+str2
t=0;
for(int i=1;i<=m;i++)c[++t]=str1[i];
c[++t]='!';
for(int i=1;i<=n;i++)c[++t]=str2[i];
}
int z1[N+1+M+1]/*a,b正着的z数组*/,z2[N+1+M+1]/*a,b倒着的z数组*/;
void z_init(int z[]){//Z算法
int zl=0,zr=0;
for(int i=2;i<=t;i++)
if(zr<i){
while(i+z[i]<=t&&c[i+z[i]]==c[1+z[i]])z[i]++;
if(z[i])zl=i,zr=i+z[i]-1;
}
else if(i+z[i-zl+1]<=zr)z[i]=z[i-zl+1];
else{
z[i]=zr-i+1;
while(i+z[i]<=t&&c[i+z[i]]==c[1+z[i]])z[i]++;
zl=i;zr=i+z[i]-1;
}
}
int lft[M+1],rit[M+1];
vector<int> dadd[M+1],ddel[N+1];//差分
multiset<int> st;
int main(){
cin>>n>>m>>s>>a+1>>b+1;
memcpy(ra+1,a+1,n+1);reverse(ra+1,ra+n+1);
memcpy(rb+1,b+1,m+1);reverse(rb+1,rb+m+1);
con(b,a);z_init(z1);
con(rb,ra);z_init(z2);
if(s>=m)//第1种情况
for(int i=1;i<=n;i++)
if(z1[m+1+i]==m){
int l=max(1,i-(s-m)),r=l+s;
if(r+s-1<=n)return cout<<"Yes
"<<l<<" "<<r,0;
r=min(n,i+s-1)-s+1;l=r-s;
if(l>=1)return cout<<"Yes
"<<l<<" "<<r,0;
}
//第2种情况
for(int i=1;i<=n;i++){//对lft影响
int l=max(s-(i-1),1),r=z1[m+1+i];
if(l>r)continue;
dadd[l].pb(i-s);if(r<m)ddel[r+1].pb(i-s);
}
st.insert(inf);//初始化
for(int i=1;i<=m;i++){//递推差分求lft
for(int j=0;j<dadd[i].size();j++)st.insert(dadd[i][j]);
for(int j=0;j<ddel[i].size();j++)st.erase(st.find(ddel[i][j]));
lft[i]=*st.begin()+i;
}
for(int i=1;i<=m;i++)dadd[i].clear(),ddel[i].clear();//数据不清空，爆零两行泪
for(int i=1;i<=n;i++){//对rit影响
int l=max(s-(n-i),1),r=z2[m+1+rev_pos(i)];
if(l>r)continue;
dadd[l].pb(i+1);if(r<m)ddel[r+1].pb(i+1);
}
st.clear();st.insert(-inf);//初始化
for(int i=1;i<=m;i++){//递推差分求rit
for(int j=0;j<dadd[i].size();j++)st.insert(dadd[i][j]);
for(int j=0;j<ddel[i].size();j++)st.erase(st.find(ddel[i][j]));
rit[i]=*--st.end()-i;
}
// for(int i=1;i<=m;i++)printf("lft[%d]=%d rit[%d]=%d
",i,lft[i],i,rit[i]);
for(int i=0;i<=s;i++)if(0<=m-i&&m-i<=s)
if(lft[i]+s-1<rit[m-i])//不相交
return cout<<"Yes
"<<lft[i]<<" "<<rit[m-i],0;
puts("No");
return 0;
}