http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4110
题意:反转某一个区间的子字符串,使得两个字符串相同
题解:
1、判断两个字符串是否完全相同;
2、完全相同则Manacher's Algorithm求回文字符串数量;
3、不完全相同则分别从头从尾至不相同得到区间[l,r],反转这个区间判断是否和另一个字符串相同;
4、3中不相同则ans==0;
5、3中相同则同时向两边扩张,条件是同时加1,并且相同
C++版本一
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=2000000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
ll ans,cnt,flag,temp,sum;
char a[N],b[N];
int P[N<<1];
char str;
struct node{};
ll Manacher(string s)
{
/*改造字符串*/
string res="$#";
for(int i=0;i<s.size();++i){
res+=s[i];
res+="#";
}
/*数组*/
ll ans=0;
int mi=0,right=0; //mi为最大回文串对应的中心点,right为该回文串能达到的最右端的值
for(int i=1;i<res.size();++i){
P[i]=right>i ?min(P[2*mi-i],right-i):1; //关键句,文中对这句以详细讲解
while(res[i+P[i]]==res[i-P[i]])
++P[i];
if(right<i+P[i]){ //超过之前的最右端,则改变中心点和对应的最右端
right=i+P[i];
mi=i;
}
ans+=P[i]/2;
}
return ans;
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
cin>>t;
while(t--){
//scanf("%s%s",a,b);
cin>>a>>b;
int len=strlen(a);
for(l=0;l<len&&a[l]==b[l];l++);
for(r=len-1;r>=0&&a[r]==b[r];r--);
if(l>r){
cout<<Manacher(a)<<endl;
}else{
flag=1;
for(int i=l;i<=r;i++){
if(a[i]!=b[r-i+l]){
flag=0;
break;
}
}
if(flag){
ans=1;
while(l-1>=0&&r+1<=len-1&&a[l-1]==a[r+1])ans++,l--,r++;
cout<<ans<<endl;
}else{
cout<<0<<endl;
}
}
}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<math.h>
using namespace std;
const int N=2e6+50;
char s1[N],s2[N],s[N*2];
int len[N*2];
int mi(int a,int b){
if(a<b) return a;
return b;
}
int main(){
int t,i,n,k,p,ma;
scanf("%d",&t);
while(t--){
scanf("%s%s",s1+1,s2+1);
n=strlen(s1+1);
k=1;
for(i=1;i<=n;i++) if(s1[i]!=s2[i]) k=0;
if(k){
for(i=1;i<=n+1;i++){
s[i*2]=s1[i];
s[i*2-1]='*';
}
s[0]='#';
p=ma=0;
long long ans=0;
for(i=1;i<=2*n;i++){
if(ma>i) len[i]=mi(ma-i,len[2*p-i]);
else len[i]=1;
while(s[i+len[i]]==s[i-len[i]]) len[i]++;
if(ma<len[i]+i){
ma=len[i]+i;
p=i;
}
ans+=len[i]/2;
}
printf("%lld\n",ans);
}
else{
int l=1,r=n,ans=1;
while(s1[l]==s2[l]) l++;
while(s1[r]==s2[r]) r--;
for(i=l;i<=r;i++) if(s1[i]!=s2[r-(i-l)]) ans=0;
if(ans==0) printf("0\n");
else{
ma=1;
while(l-ma>=1&&r+ma<=n&&s1[l-ma]==s1[r+ma]) ma++;
printf("%d\n",ma);
}
}
}
return 0;
}