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 DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endifios::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 DEBUGprintf("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; }

總結

以上是生活随笔為你收集整理的Strings in the Pocket的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。