#pragma GCC optimize ("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
using pii = pair<int, int>;
template<typename T>
using prior = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using Prior = priority_queue<T>;
#define X first
#define Y second
#define ALL(x) (x).begin(), (x).end()
#define eb emplace_back
#define pb push_back
#define fastIO() ios_base::sync_with_stdio(false); cin.tie(0)
const int mod = 1E9 + 9;
const int p = 1000;
void solve() {
int n;
string s;
cin >> s, n = s.size();
if (n == 1) {cout << 1 << "\n"; return;}
int Hash[n];
for (int i = 0; i < n; ++i) Hash[i] = ((i ? Hash[i-1] : 0) * p + s[i]) % mod;
auto fastpow = [](int base, int pow, int ans = 1) {
while (pow) {
if (pow & 1) ans = ans * base % mod;
base = base * base % mod, pow >>= 1;
}
return ans;
};
auto getHash = [&](int L, int len) {
return (Hash[L+len-1] - (L ? Hash[L-1] * fastpow(p, len) % mod : 0) + mod) % mod;
};
// for (int i = 0; i < n; ++i) cerr << getHash(i, 1) << " \n"[i == n-1];
int tok = 0, ans = 0;
for (int i = 0; i < n/2; ++i) {
if (getHash(tok, i-tok+1) == getHash(n-i-1, i-tok+1)) {
ans += 2;
tok = i + 1;
if (n%2 and i == n/2-1) ++ans;
}
else if (i == n/2-1) ++ans;
}
cout << ans << "\n";
}
int32_t main() {
fastIO();
int t;
cin >> t;
while (t--) solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
512 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
7 ms |
384 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
512 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
7 ms |
384 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
4 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
512 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
7 ms |
384 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
4 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
7 ms |
512 KB |
Output is correct |
11 |
Correct |
7 ms |
560 KB |
Output is correct |
12 |
Correct |
8 ms |
512 KB |
Output is correct |
13 |
Correct |
6 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
512 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
7 ms |
384 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
4 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
7 ms |
512 KB |
Output is correct |
11 |
Correct |
7 ms |
560 KB |
Output is correct |
12 |
Correct |
8 ms |
512 KB |
Output is correct |
13 |
Correct |
6 ms |
512 KB |
Output is correct |
14 |
Correct |
353 ms |
20780 KB |
Output is correct |
15 |
Correct |
275 ms |
15636 KB |
Output is correct |
16 |
Correct |
535 ms |
19708 KB |
Output is correct |
17 |
Correct |
103 ms |
11080 KB |
Output is correct |