题意:给一个只含a、b的字符串,求所有的回文不连续子序列。
manacher+FFT。
先求出所有回文序列,再减去连续子序列(即回文串)。
将a、b分开考虑,对于一个对称轴,以其为回文中心的回文序列的个数为 2^对称a、b个数-1。对称统计显然可以通过FFT求,然后再用manacher求回文串1即可。
调的好恶心啊!
2023-10-13 18:58:52
题意:给一个只含a、b的字符串,求所有的回文不连续子序列。
manacher+FFT。
先求出所有回文序列,再减去连续子序列(即回文串)。
将a、b分开考虑,对于一个对称轴,以其为回文中心的回文序列的个数为 2^对称a、b个数-1。对称统计显然可以通过FFT求,然后再用manacher求回文串1即可。
调的好恶心啊!