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

文章作者: fightinggg
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 fightinggg !
  目录