#pragma GCC optimize("O3")
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pii pair<int, int>
#define mpr make_pair
#define fi first
#define se second
#define int long long
#define Local
const int sz = 5005;
const long long inf = 1e9 + 7;
const int mod = 1e9 + 7;
template<typename Iterator>
void read(Iterator b, Iterator e) {
while (b != e) {
cin >> *b++;
}
}
int bin_pow(int x, int b) {
int res = 1;
while (b > 0) {
if (b & 1) {
res = (res * x) % mod;
}
x = (x * x) % mod;
b >>= 1;
}
return res;
}
int p[sz], invp[sz], shash[sz];
int pp = 31;
int get_hash(int l, int r) {
return ((shash[r] - shash[l - 1] + mod) * invp[l - 1]) % mod;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef Local
// freopen("main.in", "r", stdin);
// freopen("main.out", "w", stdout);
#endif
p[0] = 1;
for (int i = 1; i < sz; i++) {
p[i] = (p[i - 1] * pp) % mod;
}
for (int i = 0; i < sz; i++) {
invp[i] = bin_pow(p[i], mod - 2);
}
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
int n = s.size();
for (int i = 0; i <= n; i++) shash[i] = 0;
for (int i = 0; i < n; i++) {
shash[i + 1] = (shash[i] + (p[i] * (s[i] - 'a' + 1)) % mod) % mod;
}
int l = 1, r = n, res = 0;
for (int i = 1; i <= n / 2; i++) {
if (get_hash(l, i) == get_hash(n - i + 1, r)) {
res += 2;
l = i + 1;
r = n - i;
}
}
if (l <= r) res++;
cout << res << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |