给一个串 s = s1s2... sn，你可以选定其一个非空子串，然后将该子串翻转。具体来说，若选定的子串区间为 [l, r]（1 ≤ l ≤ r ≤ n），则翻转后该串变为 s1s2... sl - 1srsr - 1... slsr + 1... sn。

请你回答仅通过一次上述操作后，s 是否能变成回文串。串 s 是回文串，当且仅当它从左至右读出与从右至左读出完全相同，即 s1s2... sn = snsn - 1... s1。

解析：

我们只需要找到不对称的那一部分在进行每一位反转，这时候我们可以用 O（1）的时间复杂度进行优化。hash函数。

公式：get(l,r) - get(l,i)*p[r -i] + get2(l,i)*p[r-i] 其中 p[r - i ]是 进行了 p倍

#include<bits/stdc++.h>
#define ull int
typedef long long ll;
using namespace std;
const int mod = 1e9+7;
const int N=5e5+7;
int n,m,k;
char str[N];
int h1[N],h2[N],p[N];void init() {p[0]=1;for(int i=1;i<=500000;i++) p[i]=(ll)p[i-1]*131%mod;
}void init(int l,int r) {	h1[l-1]=0;for(int i=l;i<=r;i++) {h1[i]=((ll)h1[i-1]*131+str[i])%mod;}h2[r+1]=0;for(int i=r;i>=l;i--) {h2[i]=((ll)h2[i+1]*131+str[i])%mod;}
}int get1(int l,int r) {return ((h1[r]-(ll)h1[l-1]*p[r-l+1]%mod)+mod)%mod;
}int get2(int l,int r) {return ((h2[l]-(ll)h2[r+1]*p[r-l+1])%mod+mod)%mod;
}bool check1(int l,int r,int i) {int hs1=(((ll)get1(l,r)-(ll)get1(l,i)*p[r-i]+(ll)get2(l,i)*p[r-i])%mod+mod)%mod;int hs2=(((ll)get2(l,r)-(ll)get2(l,i)+(ll)get1(l,i))%mod+mod)%mod;return hs1==hs2;
}bool check2(int l,int r,int i) {int hs1=(((ll)get1(l,r)-(ll)get1(i,r)+(ll)get2(i,r))%mod+mod)%mod;int hs2=(((ll)get2(l,r)-(ll)get2(i,r)*p[i-l]+(ll)get1(i,r)*p[i-l])%mod+mod)%mod;return hs1==hs2;
}void solve()
{scanf("%s",str+1);n=strlen(str+1);int l=1,r=n;while(l<=r&&str[l]==str[r]) l++,r--;if(l>r) {printf("Yes\n");return ;}init(l,r);bool flag=false;for(int i=l;i<r;i++) {if(check1(l,r,i)) flag=true;if(flag) break;}for(int i=r;i>l;i--) {if(check2(l,r,i)) flag=true;if(flag) break;}if(flag) printf("Yes\n");else printf("No\n");}
int main()
{init();int t; cin >> t;while(t--){solve();}return 0;} 

时间复杂度为：O(n)；