$ShikandCopyingString$Shik and Copying String

题目描述请点击题目链接 .

$最初想法$最初想法

先检查 无解情况 骗点分 .
因为只有前面才会对后面造成影响, 所以 从后向前处理,
分情况讨论

1. $S_i=T_i$Si​=Ti​, 无覆盖, 跳过 .
2. $S_i=T_i$Si​=Ti​, 有相应覆盖, 跳过 .
3. $S_i=T_i$Si​=Ti​, 无相应覆盖, 查找 $(1,Min\_L)$(1,Min_L) 内 $S_t=T_i$St​=Ti​ 的 $t$t, 从 $t$t 向后覆盖, 若找不到, 无解. 若有其他覆盖, $Ans++$Ans++ .
4. $S_i\ne T_i$Si​̸​=Ti​, 有相应覆盖, 跳过 .
5. $S_i\ne T_i$Si​̸​=Ti​, 无相应覆盖, 同 $3.$3.

对影响的消除部分有细节 .
栈不要开 $1e6!!!$1e6 !!!, 会 $MLE$MLE .

$正解部分$正解部分

大体思路跟上方差不多, 我怎么就没想到画二维图?!

将过程图画出来, 发现字母之间覆盖关系马上就清楚了许多 .

1. 字母覆盖折线不能相交.
2. 覆盖折线要尽量 $\mathrm{\"}贴\mathrm{\"}$"贴" 着走 .

考虑一个折线的产生对以后的折线有什么影响,
看到图中红色箭头部分, 是 $c$c 产生的折线使得 $a$a 产生的折线不得不弯曲一次,

这也可以看成是 $c$c 的折线拐点 传递 到了 $a$a, 使得 $a$a 产生第 $2$2 个拐点 .
假设又有新的折线加入, 可能又会接着 $a$a 的第二个拐点继续传, 进而产生第 $3$3个拐点, 同时 $a$a 的第一个拐点又会传递产生 新折线 的第 $2$2 个拐点 , 以此类推 .

$设$设 当前 从后往前 遍历到了 $i$i, 且在 $(1,最后的覆盖起点)$(1,最后的覆盖起点) 中满足 $S_t=T_i$St​=Ti​ 的最大的编号为 $t$t,

前方某个折线的 $覆盖起点$覆盖起点 为 $bg$bg, 传递了 $len$len 次,

则当且仅当 $bg-len+1\le i$bg−len+1≤i 的时候那个折线才会对现在造成影响,

于是使用队列维护从后往前的操作中产生的折线, 每次弹出无用的折线, 剩下的折线对当前 $i$i 造成影响,
设队列大小为 $q\_size$q_size, 则会多产生 $q\_size$q_size 个拐点 , 加上 当前折线 产生的 $1$1 个拐点, 总共有 $q\_size+1$q_size+1 个拐点 .

$END$END .

$实现部分$实现部分

使用队列维护 .
注意当 $i=Min\_l$i=Min_l 时折线只有一个转折点 .

#include<bits/stdc++.h>
#define reg register

const int maxn = 1000005;

int N;

char S[maxn];
char T[maxn];

int main(){
        scanf("%d", &N);
        scanf("%s%s", S+1, T+1);
        int flag = 1;
        for(reg int i = 1; i <= N; i ++)
                if(S[i] != T[i]){ flag = 0; break ; }
        if(flag){ printf("0\n"); return 0; }
        int Min_l = N, Ans = 1;
        std::queue <int> Q;
        for(reg int i = N; i >= 1; i --){
                Min_l = std::min(i, Min_l);
                if(T[i] == T[i-1]) continue ;
                while(Min_l && S[Min_l] != T[i]) Min_l --;
                if(!Min_l){ printf("-1\n"); return 0; }
                while(!Q.empty()){
                        if(Q.front()-Q.size()+1 > i) Q.pop();
                        else break ;
                }
                Q.push(Min_l);
                if(Min_l != i) Ans = std::max(Ans, (int)Q.size() + 1);
        }
        printf("%d\n", Ans);
        return 0;
}