cf1036D

转移自老blog

cf1036D

链接

题意

        给你两个串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值的个数就是答案