一. 题目

二. 思路

• 若该串前缀和后缀有一部分成回文, 那么翻转时一定不会翻转已经成回文的部分

• 假设t位置是不等于n-t+1位置, 那么翻转的子串一定是以t开头或者n-t+1结尾, 否则翻转后也一定不是回文串

• 所以可以暴力枚举i:t~n-t+1, check(t, i)||check(i, n-t+1)

• 如何判断翻转后的值, 则利用字符串哈希, 求出前高后低head, 和前低后高tail, 注意这里求tail时是将其反过来和求head时一块求, 这样可以共用一个get_hash函数, 详见make_hash函数

• 若对于正串的(l, r)这段, 对于反串则是(n-r+1, n-l+1)

三. 代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
using LL=long long;
const int N=5e5+10, S=131, MOD=1e9+7;

int T;
int n;
char str[N];

class StrHash
{
public:
    LL head[N], tail[N], sys[N];
public:
    StrHash()
    {
        initIO();
    }

    void initIO()
    {//卡cin和cout
//        ios::sync_with_stdio(false);
//        cin.tie(nullptr), cout.tie(nullptr);
    }

    void makeHash()
    {
        sys[0]=1, head[0]=tail[0]=0;
        for(int i=1, j=n;i<=n;++i, --j)
        {//head abc， tail cba
            sys[i]=getMod(sys[i-1]*S);//head[i]表示以1~i这段前高后低的哈希值
            head[i]=getMod(head[i-1]*S+str[i]);//高位~低位
            tail[i]=getMod(tail[i-1]*S+str[j]);//tail是把尾当作头，把头当做尾，低位~高位
            //tail[i]表示，n ~ n-i+1这段，前高后低的哈希值，这样可以共用同一个getHash函数
        }
    }

    LL getHash(LL has[], int l, int r)
    {
        // return getMod(hash[r]-hash[l-1]*sys[r-l+1]);
        return getMod(has[r]-has[l-1]*sys[r-l+1]);
    }

    LL getMod(LL x)
    {
        return (x%MOD+MOD)%MOD;
    }

    bool reverIfH(int l, int r)//翻转l~r的区间后，是否是回文串
    {
        LL h=head[n], t=tail[n];//最初全串前后哈希值
        //减去正串*进制差值, +上倒串对应位置*进制差值:......rxxxx  n-r就求出了xxx需要乘的进制
        LL nh=getMod(h-getHash(head, l, r)*sys[n-r]+getHash(tail, n-r+1, n-l+1)*sys[n-r]);
        LL nt=getMod(t-getHash(tail, n-r+1, n-l+1)*sys[l-1]+getHash(head, l, r)*sys[l-1]);
        //减去倒着的加上正着的, n-(n-l+1)->求出进制差:l-1
        return nh==nt;
    }
}sh;

int main()
{
    cin>>T;
    while(T--)
    {
        scanf("%s", str+1);
        n=strlen(str+1);

        sh.makeHash();
        if(sh.head[n]==sh.tail[n])
        {
            puts("Yes");
            continue;
        }

        int t;
        for(int i=1;i<=n;++i)
            if(str[i]!=str[n-i+1])//找到第一次不相等的地方
            {
                t=i;
                break;
            }

        bool ifH=false;
        for(int i=t;i<=n-t+1;++i)//暴力翻转所有情况
            if(sh.reverIfH(t, i)||sh.reverIfH(i, n-t+1))
            {
                ifH=true;
                break;
            }
        if(ifH) puts("Yes");
        else puts("No");
    }
}