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条性质到底是什么意思……
万分感谢!