2019浙江省赛 K Strings in the Pocket

链接 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4110

题意：给你两个字符串s和t，问你有多少种方法，在仅翻转一次s的子串后使得两个串相同。

题解：分两种情况。
1.两个串不同
我们先找到两个串不同点的边界值l,r，也就是最左边的那个不同点和最右边的那个不同的点。
显然可得如果翻转后两个串相同的话，那最小的翻转区间就是并且必须是[l,r].
反证明如下：
如果我们翻转区间的左端点大于l，或者右端点小于r，那 l / r 肯定没有改变，也就是说翻转完以后两个串不可能相同。
而如果我们以 l 为左端点，以x（x>r）为右端点，那我们可知s[x]=t[x]。假如翻转后两个串相等，那就会有s[l]=t[x],s[x]=t[l] ,加上s[x]=t[x] ,得出s[l]=t[l],与我们s[l]!=t[l]的条件矛盾。r同理。
然后我们从l，r向内递推判断翻转后是否相等，也就是：

while(L<=R&&L>=0&&R<len1){
    if(s[L]!=t[R]||s[R]!=t[L]){
        f=0;
        break;
    }
    L++,R--;
}

如果我们得到[l,r]翻转之后能使得两个串相同，那我们接下来就可以尝试往外拓展，

ans=0;
while(s[l]==t[r]&&s[r]==t[l]&&l>=0&&r<len1){
    ans++;
    l--,r++;
}

这样就能得到答案。

2.两个串完全相同
该情况涉及到一个算法：Manacher
不会的可以先去看看这篇博客：https://blog.csdn.net/happyrocking/article/details/82622881
Manacher算法实现的就是求出以字符串每个点（包括两个点之间的边界）为中心的最大回文串长度。时间复杂度是O(n)。
如果两个串相同，那我们只要翻转s串中任意一个回文串，这两个串就会保持原状，而使用Manacher算法能让我们在线性时间内求出每个点为中心的最大回文串长度。
对于任意一个中心点，我们翻转半径小于该点最大回文串半径的字串，就相当于翻转了一个回文串，原串保持不变，因此在该点我们可以进行的操作数x即为该点最大回文串半径的值。

for(int i=1;i<len2;i++){//len2为Manacher处理过后的串长。
    ans+=p[i]/2;//p[i]为以该点为中心的最大回文串长+1，因此我们除以2就能得到半径。
}

完整代码：

#include<stdio.h>
#include<string.h>
const int N=4e6;
char str[N<<1];
int p[N];
int len2,len1;
char s[N],t[N];
int min(int a,int b){
    return a<b?a:b;
}
int max(int a,int b){
    return a>b?a:b;
}
void Manacher(){
    for(int i=0;i<len1*2+4;i++)p[i]=0;
    str[0]='$',str[1]='#';
    for(int i=0;i<len1;i++){
        str[i*2+2]=s[i];
        str[i*2+3]='#';
    }
    int mx=0,id=0;
    len2=len1*2+2;
    str[len2]='#';
    for(int i=1;i<len2;i++){
        p[i]=i<mx?min(p[2*id-i],mx-i):1;
        while(str[i+p[i]]==str[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);
        len1=strlen(s);
        int l=len1,r=-1,flag=1;
        for(int i=0;i<len1;i++){
            if(s[i]!=t[i]){
                l=min(l,i);
                r=max(r,i);
                flag=0;
            }
        }
        if(flag){
            Manacher();
            long long ans=0;
            for(int i=1;i<len2;i++){
                ans+=p[i]/2;
            }
            printf("%lld\n",ans);
        }
        else{
            int L=l,R=r;
            int f=1;
            while(L<=R&&L>=0&&R<len1){
                if(s[L]!=t[R]||s[R]!=t[L]){
                    f=0;break;
                }
                L++,R--;
            }
            int ans=0;
            if(f==0){
                ans=0;
            }
            else{
                ans=0;
                while(s[l]==t[r]&&s[r]==t[l]&&l>=0&&r<len1){
                    ans++;
                    l--,r++;
                }
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}