Strings in the Pocket (思维+manacher)

题目链接：https://cn.vjudge.net/problem/ZOJ-4110

题意：给你两个串,可以翻转s串的一个区间,问有多少对l,r使得翻转后的s串等于t串

思路：

• 当s串和t串相同的时候，跑一遍马拉车，有多少回文串就有多少种
• 当s串和t串不同的时候，就更简单了

1. 当s和t只有1个字符不同时，无论怎么翻转都不可能相同，0种
2. 当s和t有2个及以上字符不同时，先找出左边第一个不同的和右边第一个不同的，判断这个区间翻转能不能使s和t相同。       如果能，向两边扩展，直到不能扩展；否则就是0

***的题，***的自己。

可能有的人会想（比如我自己）如果[L,R]翻转不行，那么有没有可能[L1,R](L1<L)或者[L,R1](R1>R)这个区间可以呢？

这样想下去就会觉得这道题的复杂度会暴涨（所以这道题当时放弃了，***）

但是稍微想想就知道这是不可能的

假设[L1,R]区间可以,所以s[L1]==t[R],s[R]==t[L1]

因为L1<L,所以s[L1]==t[L1]

所以s[R]=t[L1]=s[L1]=t[R]

推出来s[R]==t[R],而R是右边第一个不相同的位置，矛盾

假设不成立

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<list>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;
const int N=2e6+5;
char s[N],t[N]; 
char a[N<<1];
int p[N<<1];
void manacher(char s[],int len){
	int l=0;
	a[l++]='$';
	a[l++]='#';
	for(int i=0;i<len;i++){
		a[l++]=s[i];
		a[l++]='#';
	}
	a[l]=0;
	int mx=0,id=0;
	for(int i=0;i<l;i++){
		p[i]=mx>i?min(p[2*id-i],mx-i):1;
		while(a[i+p[i]]==a[i-p[i]]) p[i]++;
		if(i+p[i]>mx){
			mx=i+p[i];
			id=i;
		}
	}
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
    	scanf("%s%s",s,t);
        int len=strlen(s);
    	int l=0,r=len-1;
    	for(l;l<len;l++){
    	    if(s[l]!=t[l]) break;
	}
	for(r;r>=0;r--){
	    if(s[r]!=t[r]) break;
	}
	if(l==r) printf("0\n");
	else if(l>r){
	     manacher(s,len);
	     ll ans=0;
	     for(int i=0;i<2*len+2;i++){
		ans+=p[i]/2;
	     }
	     printf("%lld\n",ans);
	}
	else{
	    if(s[l]==t[r]&&s[r]==t[l]){
	        ll ans=1;
		bool flag=true;
		for(int i=l+1,j=r-1;i<r&&j>l;i++,j--){
		    if(s[i]!=t[j]){
		    flag=false;
		    break;
		    }
	         }
		if(flag){
	           for(int i=l-1,j=r+1;i>=0&&j<len;i--,j++){
			if(t[i]==t[j]) ans++;
			else break;
		   }
		   printf("%lld\n",ans);
		}
		else printf("0\n");
	  }
	  else printf("0\n");
       }
   }
   return 0;
}