http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=6012
题意：问选字符串s的一子串反转一次得到t的方案数；
思路：s和t相同就是回文子串长度的一半，否则找最长的不相等位置，先看能不能等到t，不能就是ans=0，能就向两边扩展。
反思：多组数据不能memset！！！会tle的！！
#include<algorithm> #include<set> #include<queue> #include<cmath> #include<cstring> #include<iostream> #include<set> #include<vector> #include<queue> #include<cmath> #include<cstdio> #include<map> #include<stack> #include<string> #include<bits/stdc++.h> using namespace std; #define sfi(i) scanf("%d",&i) #define pri(i) printf("%d\n",i) #define sff(i) scanf("%lf",&i) #define ll long long #define ull unsigned long long #define mem(x,y) memset(x,y,sizeof(x)) #define INF 0x3f3f3f3f #define eps 1e-16 #define PI acos(-1) #define lowbit(x) ((x)&(-x)) #define zero(x) (((x)>0?(x):-(x))<eps) #define fl() printf("flag\n") #define MOD(x) ((x%mod)+mod)%mod #define endl '\n' #define pb push_back #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r #define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) const int maxn=2e6+9; const int mod=1e9+7; inline ll read() { ll f=1,x=0; char ss=getchar(); while(ss<'0'||ss>'9') { if(ss=='-')f=-1;ss=getchar(); } while(ss>='0'&&ss<='9') { x=x*10+ss-'0';ss=getchar(); } return f*x; } char Ma[maxn*2]; int Mp[maxn*2]; char s[maxn],t[maxn]; ll Manacher(char s[],int len) { //mem(Mp,0); int l=0; Ma[l++]='$'; Ma[l++]='#'; for(int i=0;i<len;i++) { Ma[l++]=s[i]; Ma[l++]='#'; } for(int i=0;i<=l+10;i++) Mp[i]=0; Ma[l]=0; int mx=0,id=0; for(int i=0;i<l;i++) { Mp[i]=mx>i?min(Mp[2*id-i],mx-i):1; while(Ma[i+Mp[i]]==Ma[i-Mp[i]]) Mp[i]++; if(i+Mp[i]>mx) { mx=i+Mp[i]; id=i; } } ll ans=0; for(int i=0;i<l;i++) { ans+=(ll)Mp[i]/2; } return ans; } int main() { FAST_IO; //freopen("input.txt","r",stdin); int T; cin>>T; while(T--) { cin>>s>>t; ll ans=0; int n=strlen(s); int l=0,r=n-1; while(l<n&&s[l]==t[l]) l++; while(r>=0&&s[r]==t[r]) r--; if(l==n) { ans=Manacher(s,n); cout<<ans<<endl; } else { ans=1; for(int i=l;i<=r;i++) { if(s[i]!=t[l+r-i]) { ans=0; break; } } if(ans) { ans=1; l--; r++; while(l>=0&&r<n&&s[l]==t[r]&&s[r]==t[l]) l--,r++,ans++; } cout<<ans<<endl; } } return 0; }
