给你两个长度为 n n n 的小写字母字符串 s s s 和 t t t。你可以翻转 t t t 的若干个不相交的区间，要求最终 s s s 和 t t t 相同。问你最少翻转几个区间，并输出方案。
1 ≤ ∣ S ∣ = ∣ T ∣ ≤ 500000 1leq|S|=|T|leq 500000 1≤∣S∣=∣T∣≤500000 。
题解我们把两个串合并为一个新串 A A A ，满足 A 2 i = S i , A 2 i + 1 = T i A_{2i}=S_i,A_{2i+1}=T_i A2i=Si,A2i+1=Ti （ i ∈ { 0 , 1 , . . . , ∣ S ∣ − 1 } iin{0,1,...,|S|-1} i∈{0,1,...,∣S∣−1}），答案就是把 A A A 分割成若干偶数长度回文串，长度 > 2 >2 >2 的回文串最小个数。
可以很容易地想出朴素DP，
d
p
[
i
]
=
min
A
[
j
.
.
.
i
]
回
文
{
d
p
[
j
−
1
]
+
[
i
>
j
+
1
]
}
dp[i]=min_{A[j...i]回文}{dp[j-1]+[i>j+1]}
dp[i]=A[j...i]回文min{dp[j−1]+[i>j+1]}
枚举回文串的过程可以用回文自动机快速完成。
但这个还是
O
(
n
2
)
O(n^2)
O(n2) 的，于是我们想利用回文串的性质优化：
如果 fail 和原长度相差过小，意味着后面有一段等差数列，我们用前缀和优化，可以一次性考虑一整个等差数列。对于每个回文串，fail 的等差数列只有
O
(
log
)
O(log )
O(log) 个。
前缀和优化的方法有很多种，这里就不详细展开了。时间复杂度 O ( n log n ) O(nlog n) O(nlogn)
CODE这里提供了一种巧妙的实现方式
#include
