Strings in the Pocket

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;
}