AGC007F Shik and Copying String

Link
从上到下按时间倒序写出所有串，从右往左考虑。
找到\(t_i\)在\(s\)中的匹配字符\(s_p\)，我们把这个字符的移动过程画一条线，这条线只能向上/向右走。显然向右走的放到越前面越优。记一个偏移量和一个前缀和即可维护。
如果\(p\le 0\)那么说明无解。

#include<cstdio>
#include<algorithm>
const int N=1000007;
char s[N],t[N];int n,ans,sum[N];
int main()
{
    scanf("%d%s%s",&n,s+1,t+1);
    for(int i=n,f=0,k=0,p=n;i;--i)
    {
    f+=sum[i+k];
    if(p>i||t[i]^s[p])
        {
        for(;p>0&&(p>i||t[i]^s[p]);--p);
        if(p==i) continue;
        if(p<=0) return !printf("-1");
        ++k,++f,sum[i+k-1]=0,--sum[p+k-1];
        }
    ans=std::max(ans,f);
    }
    printf("%d",ans);
}

AGC007F Shik and Copying String

原文：https://www.cnblogs.com/cjoierShiina-Mashiro/p/12274680.html