社区讨论

有没有好心人可以帮我讲一下P3501 manacher的dp优化我没看懂……

2023/04/15 22:03灌水区参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

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

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

CPP

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条性质到底是什么意思……

万分感谢！

共 0 条回复，欢迎继续交流。

正在加载回复...