#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
long long mod = 1488148811;
long long p = 2585241;
vector<long long> h;
vector<long long> step;
long long hesh(long long l, long long r) {
return ((h[r + 1] - (h[l] * step[r - l + 1]) % mod) % mod + mod) % mod;
}
int main() {
long long t;
cin >> t;
step.resize(100001);
step[0] = 1;
for (long long i = 1; i < 100001; i++) {
step[i] = (step[i - 1] * p) % mod;
}
for (long long gh = 0; gh < t; gh++) {
long long n;
string s;
cin >> s;
n = s.size();
if (n == 1) {
cout << 1 << '\n';
continue;
}
h.assign(n + 1, 0);
for (long long i = 0; i < n; i++) {
h[i + 1] = ((h[i] * p) % mod + s[i]) % mod;
}
long long ans = 0;
long long l1 = 0, r1 = 0, l2 = n - 1, r2 = n - 1;
while (true) {
if (hesh(l1, r1) == hesh(l2, r2)) {
ans += 2;
l1 = r1 + 1;
r1++;
r2 = l2 - 1;
l2--;
}
else {
r1++;
l2--;
}
if ((l1 <= l2 && l2 <= r1) || (l1 <= r2 && r2 <= r1)) {
ans++;
break;
}
if (l1 > r2) {
break;
}
}
cout << ans << '\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... |