Problem - K - Codeforces

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

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

Input

注意：本题包含多组测试数据。

第一行包含一个整数 T（1 ≤ T ≤ 5 × 105），表示数据组数。

接下来的 T 行，每行包含一个仅由英文小写字母组成的字符串 s，含义见题目描述，且串长 |s| 满足 1 ≤ |s| ≤ 5 × 105。

保证字符串总长 

 不超过 5 × 105。

Output

对于每组测试数据，输出一行一个字符串，若仅通过一次操作后 s 能变成回文串，则输出 Yes，否则输出 No，大小写不敏感。

Sample 1

4
abba
bacad
abacbaa
aabadcdca

Yes
No
Yes
Yes

Note

第一组数据中，abba 翻转带下划线的子串得到回文串 abba。

第二组数据中，无论如何翻转子串，都不能得到回文串。

第三组数据中，abacbaa 翻转带下划线的子串得到回文串 aabcbaa。

第四组数据中，aabadcdca 翻转带下划线的子串得到回文串 acdabadca。

 题解:

首先如果首尾开始找,相同字符肯定不用反转,找到第一个不同的,即为标记f

反转也有两种情况,是从左边边界反转,还是从右边边界反转,两种情况均要考虑

左边界和右边界为起点时枚举终点,直接去写肯定是不行的

所以要用到 字符串哈希,先正反预处理字符串,然后线性时间判断

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
using namespace std;
#define int long long
const int N = 6e5 + 10; 
int n;
int h1[N];
int h2[N];
int p[N];
int x = 133331;
int mod = 1e9 + 7;
char a[N];
void init()
{h1[0] = a[0];p[0] = 1;for(int i = 1;i <= n+1;i++){h1[i] = (h1[i-1]*x%mod + a[i])%mod;p[i] = p[i-1]*x%mod;}h2[n+1] = 0;h2[n] = a[n];for(int i = n - 1;i >= 0;i--){h2[i] = (h2[i+1]*x%mod + a[i])%mod;}
}
int get1(int l,int r)
{return (h1[r] - h1[l-1]*p[r-l+1]%mod + mod)%mod;
}
int get2(int l,int r)
{return (h2[l] - h2[r+1]*p[r-l+1]%mod + mod)%mod;
}
int check(int l,int r)
{int hs1 = (get1(0,n) - get1(l,r)*p[n-r]%mod + get2(l,r)*p[n-r]%mod + mod)%mod;int hs2 = (get2(0,n) - get2(l,r)*p[l]%mod + get1(l,r)*p[l]%mod + mod)%mod;return hs1 == hs2;
}
void solve()
{cin >> a;n = strlen(a) - 1;init();int f = -1;for(int i = 0;i <= n;i++){if(a[i] != a[n - i]){f = i;break;}}if(f == -1){cout <<"YES\n";return ;}for(int i = f + 1;i <= n - f;i++){if(check(f,i)||check(i,n - f)){cout <<"YES\n";return ;}}cout <<"NO\n";
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t = 1;cin >> t;while(t--){solve();} 
}
//3 F
//5 B
//6 F
//9 F
//10 B
//12 F
//15 FB
//18 FB