传送：

题意：给定两个串$S$和$T$，可以翻转$S$串中的任意一个子段，得到$T$。问，可以翻转的方案书有多少？

数据范围：多组数据。$1\leq|S|\leq2\times10^5$，$\sum|S|\leq2\times10^7$。

分析：很明显需要分类讨论$S$与$T$比较的各种情况。

首先需要判断$S$串从左和从右找到与$T$开始不同的位置。

1. $S$不可以翻转成$T$：就是指$S$串中不同的那一段不可以通过翻转得到$T$，方案数为0。
2. $S$与$T$不同的“中间”那一段可以通过翻转得到对应$T$的那一段。这个时候需要向外扩展判断最长可以扩展到的位置。
3. $S$与$T$完全相同，这个时候就需要通过manacher来求解整个串内回文子串的个数。

代码：

1. 不分奇偶讨论的manacher

1 #include
     
       2 using namespace std; 3 typedef long long ll; 4 const int maxn=2e6+10; 5 char S[maxn],T[maxn],s[maxn*2]; 6 int p[maxn*2],len; 7 int init(){ 8     s[0]=s[1]='#'; 9     for (int i=0;i
      
       =0) r--;36         if (l==r){printf("0\n"); continue;}37         if (l
       
        =0 && r
       
      
     

　　2.分奇偶讨论的manacher

1 #include
     
       2 using namespace std; 3 typedef long long ll; 4 const int maxn=2e6+10; 5 char S[maxn],T[maxn]; 6 int odd[maxn],eve[maxn],len; 7 ll manacher(){ 8     int l=-1,r=-1,x; 9     ll ans=0;10     for(int i=0;i
      
       r) x=1;13         else x=min(odd[l+r-i],r-i);14         while (i-x>=0 && i+x
       
        r) {r=i+x-1;l=i-x+1;}18     }19     l=r=-1;20     for(int i=0;i
        
         r) x=0;23         else x=min(eve[l+r-i+1],r-i+1);24         while (i-x-1>=0 && i+x
         
          =r) {l=i-x;r=i+x-1;}28     }29     return ans;30 }31 int main(){32     int t; scanf("%d",&t);33     while (t--){34         scanf("%s",S);35         scanf("%s",T);36         len=strlen(S);37         int l=0,r=len-1; ll ans=0;38         while (S[l]==T[l] && l
          
           =0) r--;40 if (l==r){printf("0\n"); continue;}41 if (l
           
            =0 && r