有没有好心人可以帮我讲一下P3501 manacher的dp优化 我没看懂……
  • 板块灌水区
  • 楼主行动欲望π
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/4/15 22:03
  • 上次更新2023/10/23 18:21:39
查看原帖
有没有好心人可以帮我讲一下P3501 manacher的dp优化 我没看懂……
377578
行动欲望π楼主2023/4/15 22:03

 4、显然,以竖线为中心,对称位置上的数字为中心所成满足条件的子串个数相同(举例:11|00,中间的1和0对称,以它们各自为中心,所成满足条件的子串个数都是0。)。

 性质2、3明摆着很符合回文串的分半判断的性质!而且4性质恰好对应了manacher的dp优化初值的骚操作!

if(i<mx)p[i]=min(p[id*2-i],mx-i);
       while(i+p[i]+1<=n&&i-p[i]>=1&&s[i+p[i]+1]!=s[i-p[i]])p[i]++;
       if(i+p[i]>mx)mx=i+p[i],id=i;

具体就是这个 这个第4条性质到底是什么意思……

万分感谢!

2023/4/15 22:03
加载中...