zcmimi's blog

arrow_backmanacher共1篇文章

avatar
zc
2020-07-05 13:10:00
查看原题

点击跳转

首先找位置对称的回文子序列个数(多项式求)

由于不能连续,所以减去对称回文子串个数(manacher求)

设字符串为S,|S|=n

假设S_i作为一个子序列的对称中心,x=\sum_{j=1\le j\le i-1}[S_{i-j}=S_{i+j}]

那么以i为中心位置的方案数为2^{x+1}-1

A_i=[S_i=a],B_i=[S_i=b]

那么\displaystyle (A*A)_i=A_i*A_i=\sum_{j=0}^nA_jA_{i-j}就是对称中心为位置\frac i2的两端为a的数量

同理(B*B)_i就是对称中心为位置\frac i2的两端为b的数量

那么上述(A*A)_i+(B*B)_i就是对称中心为位置\frac i2x+1

如果i为偶数,x+1要减去1(对称中心是否在同个字符上)

1/1
Search
search