nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

转移自老blog

cf1036D

链接

https://codeforc.es/problemset/problem/1036/D

题意

        给你两个串s,t 
        |s|<3e5 |t|<3e5
        允许对两个串进行任意次如下操作：
            选一个区间，用区间和代替整个区间的元素
        最终要求达到s==t
        要求最大化s==t时候的|s|
        若不可能，输出-1

题解

        贪心做法:
            他们俩各自一个指针，往后走，谁小谁先走，不等的话，再来谁小谁先走... 相等时让计数器加1，然后一起走,有解的话输出计数器就是答案了
        其实也是尺取法
        再细细分析
        我们发现可以dp证明，dp[i]代表s串的前i项能否匹配t串的前j项，若能匹配，为dp[i]赋值j，否则定义此dp没有意义
        我们发现有意义的dp,其值关于i单调，无意义的dp，其判断依据，也关于i单调
        于是可以O（n)完成dp
        有意义的dp值的个数就是答案