1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 500010
#define ll long long
#define ldb long double
using namespace std;
int n;
char c[maxn], s[maxn];
struct Hash {
const int base = 10;
const ll p = 212370440130137957;
inline ll mul(ll x, ll y) {
return (x * y - (ll) ((ldb) x / p * y) * p + p) % p;
}
ll pow[maxn], h[maxn];
void init(char *s) {
int l = strlen(s + 1);
pow[0] = 1; for (int i = 1; i <= l; ++i) pow[i] = mul(pow[i - 1], base);
for (int i = 1; i <= l; ++i)
h[i] = (mul(h[i - 1], base) + s[i] - 'a' + 1) % p;
}
ll get(int l, int r) {
return (h[r] - mul(h[l - 1], pow[r - l + 1]) + p) % p;
}
} _, __;
void work() {
cin >> c + 1; int p = 1; n = strlen(c + 1);
while (p <= n - p + 1 && c[p] == c[n - p + 1]) ++p;
if (p > n / 2) return (void) (cout << "Yes\n");
for (int i = p; i <= n - p + 1; ++i) s[i - p + 1] = c[i];
n = n - 2 * (p - 1); s[n + 1] = '\0';
_.init(s); reverse(s + 1, s + n + 1); __.init(s);
for (int i = 1; i < n; ++i) {
if ((__.mul(__.get(1, n - i), __.pow[i]) + _.get(1, i)) % _.p ==
(__.mul(__.get(n - i + 1, n), __.pow[n - i]) + _.get(i + 1, n)) % _.p)
return (void) (cout << "Yes\n");
if ((_.mul(_.get(1, i), _.pow[n - i]) + __.get(1, n - i)) % _.p ==
(_.mul(_.get(i + 1, n), _.pow[i]) + __.get(n - i + 1, n)) % _.p)
return (void) (cout << "Yes\n");
}
cout << "No\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T;
while (T--) work();
return 0;
}
|