Atcoder [agc007F] Shik and Copying String

Description

“全”在十分愉快地给林导打工，第0天，林导给了他一个仅有小写字母构成的长度为N的字符串S0，在之后的第i天里，“全”的工作是将Si?1复制一份到一个新的字符串Si中，在接下来的描述中，我们用Si[j]表示串Si中的第j个字符

然而“全”十分不熟练，在复制的时候他容易出错。比如说在复制Si?1[j]到Si[j]的时候有时他会把Si[j]上的字符写成Si[j?1]，而不是本应被写上去的Si?1[j]，更具体一点就是新串中的字符Si[j]可能等于Si[j?1]或者Si?1[j]

这让林导很困扰，现在他给你S0和另一个长度同样为N的字符串T，希望你求出一个最小的i，能满足Si=T，如果不存在这样的i，输出?1

Input

    第一行一个正整数N第二行一个字符串S0第三行一个字符串T

Output

    输出最小的满足条件的i，无解输出?1

Solution

首先肯定尽量多覆盖相同字符的位置，然后s中对应位置尽量靠右。
因为若能碰到一个连续段的左端点则一定可以在这次操作中覆盖整段。
举个例子：
s:kazzbzzczzzz
t:kkkkaabbbbcc
最优策略为：
kazzbzzczzzz
kaaabbbccccc
kaaaaabbbbcc
kkkkaabbbbcc
共三步。
第二个例子：
s:kazzbzzczzzz
t:kkkkkkabbbcc
最优策略为：
kazzbzzczzzz
kaaabbbccccc
kaaaaabbbbcc
kkkkkaabbbcc
kkkkkkabbbcc
共四步。

可以看到需要用到的点能往后延申就往后延申。

我们从后往前枚举确定s的点到t的区间的对应关系。
设s的点为i,t的区间左端点为j$（i?=j）$。
可以看到若只有(i,j)可以两步完成。(因为i<j必然有前面的要覆盖到j-1)
维护一个队列，我们每次在队列加入(i,j)
若已有$(i_1,j_1)$，加入$(i_2,j_2)$，考虑：

1. $j_2>=i_1$，需要再加一步，答案为三步，具体可以参照第一个例子中的b和c。
2. $j_2<i_1$，明显可以同时完成，答案仍为两步，同时将$(i_1,j_1)$弹出。

接着插入$(i_2,j_2)$
这里只讨论第一种情况，因为第二种与上面相同。
现在队列中已有$(i_1,j_1),(i_2,j_2)$，加入$(i_3,j_3)$，考虑：
3. $j_3>=i_1?1$，需要再加一步，答案为四步。可以参照第二个例子。
4. $j_3<i_1?1$，弹出$(i_1,j_1)$，若$j_3<i_2$，继续弹出$(i_2,j_2)$，此时答案为两步，否则为三步。

可以看到当前的答案为队列中数(插入(i,j)后)的个数加一。

注意上文论述的都是当前情况的步数，全局答案是对所有答案取最大值。
因为可以对每个区间同时做操作。

Code

#include<bits/stdc++.h>
using namespace std;
char s[1000010];
char t[1000010];
int n,tot,ans,cnt;
queue<int>q;
bool flag=1;
int main(){
    scanf("%d%s%s",&n,s+1,t+1);for(int i=1;i<=n;i++)if(s[i]!=t[i]){
    flag=0;break;}if(flag){
    printf("0");return 0;}for(int i=n,j=n;i&&j;j--){
    while(t[j-1]==t[j]&&j) j--; i=min(i,j);while(s[i]!=t[j]&&i) i--;if(i==0){
    printf("-1");return 0;}while(q.size()&&q.front()-q.size()>=j) q.pop();if(i!=j) q.push(i);else while(!q.empty()) q.pop();ans=max(ans,(int)q.size()+1);}printf("%d",ans);
}
/* 14 azbcdeeeeggfjj aaabbccddgggff */