传送：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=6012
题意：给定两个串$S$和$T$，可以翻转$S$串中的任意一个子段，得到$T$。问，可以翻转的方案书有多少？
数据范围：多组数据。$1\leq|S|\leq2\times10^5$，$\sum|S|\leq2\times10^7$。
分析：很明显需要分类讨论$S$与$T$比较的各种情况。
首先需要判断$S$串从左和从右找到与$T$开始不同的位置。
- $S$不可以翻转成$T$：就是指$S$串中不同的那一段不可以通过翻转得到$T$，方案数为0。
- $S$与$T$不同的“中间”那一段可以通过翻转得到对应$T$的那一段。这个时候需要向外扩展判断最长可以扩展到的位置。
- $S$与$T$完全相同，这个时候就需要通过manacher来求解整个串内回文子串的个数。
代码：
- 不分奇偶讨论的manacher
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e6+;
char S[maxn],T[maxn],s[maxn*];
int p[maxn*],len;
int init(){
s[]=s[]='#';
for (int i=;i<len;i++){
s[i*+]=S[i];
s[i*+]='#';
}
len=len*+;
s[len]=;
}
void manacher(){
int id,mx=;
for (int i=;i<len;i++){
if(i<mx) p[i]=min(p[(id<<)-i],p[id]+id-i);
else p[i]=;
while (s[i-p[i]]==s[i+p[i]]) p[i]++;
if (mx<i+p[i]){
id=i;mx=i+p[i];
}
}
}
int main(){
int t; scanf("%d",&t);
while (t--){
scanf("%s",S);
scanf("%s",T);
len=strlen(S);
int l=,r=len-; ll ans=;
while (S[l]==T[l] && l<len) l++;
while (S[r]==T[r] && r>=) r--;
if (l==r){printf("0\n"); continue;}
if (l<len){
ans=;
for (int i=l;i<=r;i++)
if (S[i]!=T[l+r-i]){
ans=; break;
}
if (ans){
ans=;
l--;r++;
while (l>= && r<len && S[l]==T[r] && S[r]==T[l]){
l--;r++;ans++;
}
}
printf("%d\n",ans);
}
else{
init();
manacher(); ans=;
for (int i=;i<len;i++) ans+=(p[i]/);
printf("%lld\n",ans-);
}
}
return ;
}
2.分奇偶讨论的manacher
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e6+;
char S[maxn],T[maxn];
int odd[maxn],eve[maxn],len;
ll manacher(){
int l=-,r=-,x;
ll ans=;
for(int i=;i<len;i++)
{
if (i>r) x=;
else x=min(odd[l+r-i],r-i);
while (i-x>= && i+x<len && S[i-x]==S[i+x]) x++;
odd[i]=x;
ans+=x;
if (i+x->r) {r=i+x-;l=i-x+;}
}
l=r=-;
for(int i=;i<len;i++)
{
if(i>r) x=;
else x=min(eve[l+r-i+],r-i+);
while (i-x->= && i+x<len && S[i-x-]==S[i+x]) x++;
eve[i]=x;
ans+=x;
if (i+x>=r) {l=i-x;r=i+x-;}
}
return ans;
}
int main(){
int t; scanf("%d",&t);
while (t--){
scanf("%s",S);
scanf("%s",T);
len=strlen(S);
int l=,r=len-; ll ans=;
while (S[l]==T[l] && l<len) l++;
while (S[r]==T[r] && r>=) r--;
if (l==r){printf("0\n"); continue;}
if (l<len){
ans=;
for (int i=l;i<=r;i++)
if (S[i]!=T[l+r-i]){
ans=; break;
}
if (ans){
ans=;
l--;r++;
while (l>= && r<len && S[l]==T[r] && S[r]==T[l]){
l--;r++;ans++;
}
}
printf("%d\n",ans);
}
else{
ans=manacher();
printf("%lld\n",ans);
}
}
return ;
}