首先，我们来证明一个引理：
- 若最优解中，最终串中的字符 \(j\) 在最早来自原串中的字符 \(i\)（显然，\(i\le j,s_i=t_j\)），则称 \(j\) 的匹配是 \(i\)，则在所有的匹配方案中，\(t_j\) 会在全串存在匹配的前提下尽量选择 \(|i-j|\) 最小的的 \(s_i\) 进行匹配。
我们可以运用数学归纳法。
第一，显然所有 \(t\) 中字符的匹配单调不降，设结论在后缀对 \((i,j+1)\) 成立，那么如果 \(x<y\le i\)，\(s_x=s_y=t_j\)，因为匹配不交叉，所以用 \(s_x\) 匹配的操作 \(s_y\) 都能做，\(s_y\) 能做的 \(s_x\) 却不一定能做，并且 \(j\) 后面的都被 \(i\) 后面的匹配完了，所以 \(y\) 只要存在就一定可以选（而不会和后面产生冲突，所以对于 \((i,j)\) 成立。
接着，对于 \((i+1,j)\) 成立，\((i,j)\) 必然成立，这是显然的。
又有对后缀 \((n,n)\) 成立（没有后面的可以干扰），所以就全部成立了。
我们就可以倒着匹配跑出每个位置的最优匹配。如果匹配不存在，直接输出 \(-1\)。
到这里，就一定有解了，因为我们显然可以做 \(n\) 次倒着依次满足所有的匹配。然后考虑如何计算最小操作次数。
首先，我们构造匹配段，设 \(r_i\) 是匹配到 \(i\) 的最大的位置，那么显然最终匹配到 \(i\) 的是一段区间 \([l_i,r_i](i\le l_i)\)。
在这里，我先观察一些数据，写了一个假的贪心，我猜答案是特判掉不操作之后，每个位置被 \([i,r_i]\) 覆盖次数的最大值。但是这是一点依据都没有的假做法。
那么，我们把所有有匹配的 \(i\) 依次罗列出来，开始考虑暴力一点的做法。
我们设所有有匹配的 \(i\) 一共有 \(m\) 个，每个对应一段区间 \([a_i,b_i]\)，其中 \(a_i\) 就是原始的起点，\(b_i\) 就是 \(r_{a_{i}}\)。
然后我们把原先的操作映射上来，其实就是要通过若干次增加 \(a\) 数组的方式到达 \(b\)，我们设 \(a_{i,j}\) 表示 \(i\) 次操作之后，匹配 \(j\) 所扩展到的最右端。每次扩展的时候，\(a_{i,j}\) 必须小于 \(a_{i-1,j+1}\)（否则会完全把后一种匹配覆盖掉）
然后我们就得到了一个 \(O(n^2)\) 的做法，暴力扩展 \(a_{i,j}\) 为 \(\max\{a_{i-1,j+1}-1,a_{i-1,j},b_j\}\)，因为答案一定不超过 \(n\)，所以复杂度是 \(O(n^2)\)。
考虑优化。
我们发现，我们上面能这样做的原因是我们只需要考虑每个匹配所达到的最右端。只要最右端都符合条件，因为 \(b_i\) 是单调增的，然后前一个的最右端又不会跑到自己这边来，自己从 \(a_i\) 过来已经把这一段全部染过一次了，所以就达成目的了。
然后我们重新定义 \(t_{i,j}\) 为 \(i\) 轮操作之后 \(a_j\) 的理论最大值。也就是在只有限制条件小于 \(a_{i-1,j+1}\) 下，所能达到的最大值。
很明显，每轮操作之后，最后一个数就变成 \(+\infty\) 了。
然后我们考虑这个理论最大值和实际最大值的关系。我们发现，实际最大值只是在拓展的过程中多了一个 \(b_i\) 的限制。而这个限制一旦达到，我们这里也就达成了，不需要再往后了。然后如果 \(j+1\) 已经受限了，因为 \(b_j<b_{j+1}\)，所以我们也一定可以直接一步达到 \(b_i\)。
所以，只要 \(a_{i,j}=\min(t_{i,j},b_j)\)
考虑计算 \(t_{i,j}\) 什么时候大于等于 \(b_j\)，我们发现，因为 \(t_i\) 单调递增，所以每轮直接用 \(t_{i-1,j+1}-1\) 作为 \(t_{i,j}\) 一定最优，那么 \(k\) 轮之后就是 \(t_{i-k,j+k}-k\)。
我们成功的把问题转化成找到最小的 \(j\) 使得 \(j-i\) 次迭代之后，\(a_j-(j-i)\) 要大于等于 \(b_i\)，重新写一下，就是最小的 \(j\) 使得 \(a_j-j\ge b_i-i\)，\(j=res_i\)，\(ans=\max_{i=1}^n(res_i-i)\)
这个问题显然可以直接用树状数组求解，我们就得到了一个 \(O(n\log n)\) 的做法，也就可以通过了。
int n,r[1000005],b[1000005];
int a[1000005],m;
st s,t;
int fen[2000005];
inline void add(int x,int v){
for(;x<=n;x+=(x&(-x)))fen[x]=min(fen[x],v);
}
inline int qry(int x){
int res=m+1;
for(;x;x-=(x&(-x)))res=min(res,fen[x]);
return res;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>s>>t;
s='$'+s,t='$'+t;
if(s==t){
cout<<0<<endl;
return 0;
}
for(int i=n,j=n;i>=1&&j>=1;j--,i=min(i,j)){
while(i>=1&&s[i]!=t[j])i--;
if(!i){
cout<<-1<<endl;
return 0;
}r[i]=max(r[i],j);
}
rp(i,n)if(r[i])a[++m]=i,b[m]=r[i];
rp(i,m)a[i]-=i,b[i]-=i;
int ans=0;
rep(i,1,n)fen[i]=m+1;
per(i,1,m){
ans=max(ans,qry(n-b[i])-i);
add(n-a[i],i);
}
cout<<ans<<endl;
return 0;
}
//Crayan_r
这版代码调试了不短的时间，尤其是最后 RE 两个点的时候，主要问题在于树状数组的值域。首先，\(a_i-i\) 和 \(b_i-i\) 的值域是 \([0,n-1]\)。然后逆转偏序关系，用 \(n-a_i+i\) 来代替就可以做到 \([1,n]\) 的树状数组。但是我在一开始分析的时候，把 \(a_i-i\) 的值域当作了 \([-m,m]\)，从而使用 \(2m-a_i+1\) 代替（实际上并没有仔细思考），这样最后是 RE 两个点，最终通过是使用 \(M=10^6\) 以及 \(2M\) 的值域通过这题。但是后来经过分析，才得出了正确的结论，也就有了上面的最优版代码。
但是 \(O(n\log n)\) 不是终点！
我们发现，因为 \(a_i\) 是单调增的，所以 \(a_i-i\) 是单调不降的。也就是说，我们查找的序列是满足单调性的。可以优化掉 \(\text{Fenwick Tree}\)，直接用 \(\text{two pointers}\) 即可。
然后还有一点不起眼的小优化，我们发现，我们可以在处理匹配的同时计算答案。因为每个 \(i\) 第一次被匹配到一定是被 \(r_i\) 匹配的，所以如果我们保存每个位置有没有被匹配过就可以计算了。
但是这里还存在一个问题，我们从后往前，还不知道有多少个位置，如何知道 \(a_i-i\) 中的 \(i\) 呢？实际上，我们可以把比较 \(a_i-i\) 和 \(b_i-i\) 转化成比较 \(a_i+m-i+1\) 和 \(b_i+m-i+1\)，而后面的 \(m-i+1\) 就是从后往前跑的时候的编号。这样，我们就得到了一个 \(O(n)\) 的做法。而且不用考虑值域了。
虽然代码短又快，但还是被 14ms 的不知道哪个神仙老哥爆杀了
int n,a[1000005],cnt=0,ans=0,res[1000005];
st s,t;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>s>>t;
for(int i=n,j=n,cur=0;j>=1;j--,i=min(i,j)){
while(i>=1&&s[i-1]!=t[j-1])i--;
if(!i){
cout<<-1<<'\n';
return 0;
}if(!res[i]){
cnt++,a[cnt]=i+cnt,res[i]=1;
while(cur<cnt&&a[cur+1]>=j+cnt)cur++;
ans=max(ans,cnt-cur);
}
}cout<<ans<<'\n';
return 0;
}
//Crayan_r