#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using graph = vector<vector<int>>;
constexpr uint64_t MAXLEN = 1000005;
constexpr uint64_t mod = (1ULL << 61) - 1;
const uint64_t seed = chrono::system_clock::now().time_since_epoch().count();
const uint64_t base = mt19937_64(seed)() % (mod / 3) + (mod / 3);
uint64_t base_pow[MAXLEN];
int64_t modmul(uint64_t a, uint64_t b){
uint64_t l1 = (uint32_t)a, h1 = a >> 32, l2 = (uint32_t)b, h2 = b >> 32;
uint64_t l = l1 * l2, m = l1 * h2 + l2 * h1, h = h1 * h2;
uint64_t ret = (l & mod) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
ret = (ret & mod) + (ret >> 61);
ret = (ret & mod) + (ret >> 61);
return ret - 1;
}
void init(){
base_pow[0] = 1;
for (int i = 1; i < MAXLEN; i++){
base_pow[i] = modmul(base_pow[i - 1], base);
}
}
int slow(string& s) {
int n = s.length();
int ans = 0;
int l = 0;
int r = s.length() - 1;
string left = "";
string right = "";
bool middle = false;
bool even_middle = false;
while (l <= r) {
left += s[l];
right = s[r] + right;
if (left == right) {
ans += 2;
left = "";
right = "";
if (l == r) {
middle = true;
}
if (n % 2 == 0 && l + 1 == r) {
even_middle = true;
}
}
++l;
--r;
}
if (n % 2 == 1) {
if (middle) --ans;
else ++ans;
} else {
if (!even_middle) ++ans;
}
return ans;
}
struct PolyHash{
/// Remove suff vector and usage if reverse hash is not required for more speed
vector<int64_t> pref, suff;
PolyHash() {}
template <typename T>
PolyHash(const vector<T>& ar){
if (!base_pow[0]) init();
int n = ar.size();
assert(n < MAXLEN);
pref.resize(n + 3, 0), suff.resize(n + 3, 0);
for (int i = 1; i <= n; i++){
pref[i] = modmul(pref[i - 1], base) + ar[i - 1] + 997;
if (pref[i] >= mod) pref[i] -= mod;
}
for (int i = n; i >= 1; i--){
suff[i] = modmul(suff[i + 1], base) + ar[i - 1] + 997;
if (suff[i] >= mod) suff[i] -= mod;
}
}
PolyHash(const char* str)
: PolyHash(vector<char> (str, str + strlen(str))) {}
uint64_t get_hash(int l, int r){
int64_t h = pref[r + 1] - modmul(base_pow[r - l + 1], pref[l]);
return h < 0 ? h + mod : h;
}
uint64_t rev_hash(int l, int r){
int64_t h = suff[l + 1] - modmul(base_pow[r - l + 1], suff[r + 2]);
return h < 0 ? h + mod : h;
}
};
void solve() {
string s;
cin >> s;
int n = s.length();
PolyHash hash_s(s.c_str());
int ans = 1;
for (int i = 0; i < n/2; ++i) {
int j = i;
while (j < n/2) {
if (hash_s.get_hash(i, j) == hash_s.get_hash(n - j - 1, n - i - 1)) {
break;
}
++j;
}
i = j;
}
/* cout << ans << '\n'; */
cout << slow(s) << '\n';
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int tc; cin >> tc;
while(tc--) solve();
}
Compilation message
palindromic.cpp: In function 'void init()':
palindromic.cpp:25:23: warning: comparison of integer expressions of different signedness: 'int' and 'const uint64_t' {aka 'const long unsigned int'} [-Wsign-compare]
25 | for (int i = 1; i < MAXLEN; i++){
| ~~^~~~~~~~
palindromic.cpp: In function 'void solve()':
palindromic.cpp:117:6: warning: unused variable 'ans' [-Wunused-variable]
117 | int ans = 1;
| ^~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from palindromic.cpp:1:
palindromic.cpp: In instantiation of 'PolyHash::PolyHash(const std::vector<_Tp>&) [with T = char]':
palindromic.cpp:98:57: required from here
palindromic.cpp:83:18: warning: comparison of integer expressions of different signedness: 'int' and 'const uint64_t' {aka 'const long unsigned int'} [-Wsign-compare]
83 | assert(n < MAXLEN);
| ~~^~~~~~~~
palindromic.cpp:88:25: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long int>, long int>::value_type' {aka 'long int'} and 'const uint64_t' {aka 'const long unsigned int'} [-Wsign-compare]
88 | if (pref[i] >= mod) pref[i] -= mod;
palindromic.cpp:93:25: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long int>, long int>::value_type' {aka 'long int'} and 'const uint64_t' {aka 'const long unsigned int'} [-Wsign-compare]
93 | if (suff[i] >= mod) suff[i] -= mod;
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8020 KB |
Output is correct |
| 2 |
Correct |
10 ms |
8060 KB |
Output is correct |
| 3 |
Correct |
9 ms |
8148 KB |
Output is correct |
| 4 |
Correct |
10 ms |
8108 KB |
Output is correct |
| 5 |
Correct |
10 ms |
8080 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8020 KB |
Output is correct |
| 2 |
Correct |
10 ms |
8060 KB |
Output is correct |
| 3 |
Correct |
9 ms |
8148 KB |
Output is correct |
| 4 |
Correct |
10 ms |
8108 KB |
Output is correct |
| 5 |
Correct |
10 ms |
8080 KB |
Output is correct |
| 6 |
Correct |
9 ms |
8136 KB |
Output is correct |
| 7 |
Correct |
9 ms |
8148 KB |
Output is correct |
| 8 |
Correct |
8 ms |
8148 KB |
Output is correct |
| 9 |
Correct |
9 ms |
8148 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8020 KB |
Output is correct |
| 2 |
Correct |
10 ms |
8060 KB |
Output is correct |
| 3 |
Correct |
9 ms |
8148 KB |
Output is correct |
| 4 |
Correct |
10 ms |
8108 KB |
Output is correct |
| 5 |
Correct |
10 ms |
8080 KB |
Output is correct |
| 6 |
Correct |
9 ms |
8136 KB |
Output is correct |
| 7 |
Correct |
9 ms |
8148 KB |
Output is correct |
| 8 |
Correct |
8 ms |
8148 KB |
Output is correct |
| 9 |
Correct |
9 ms |
8148 KB |
Output is correct |
| 10 |
Correct |
15 ms |
8508 KB |
Output is correct |
| 11 |
Correct |
13 ms |
8404 KB |
Output is correct |
| 12 |
Correct |
14 ms |
8408 KB |
Output is correct |
| 13 |
Correct |
12 ms |
8380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8020 KB |
Output is correct |
| 2 |
Correct |
10 ms |
8060 KB |
Output is correct |
| 3 |
Correct |
9 ms |
8148 KB |
Output is correct |
| 4 |
Correct |
10 ms |
8108 KB |
Output is correct |
| 5 |
Correct |
10 ms |
8080 KB |
Output is correct |
| 6 |
Correct |
9 ms |
8136 KB |
Output is correct |
| 7 |
Correct |
9 ms |
8148 KB |
Output is correct |
| 8 |
Correct |
8 ms |
8148 KB |
Output is correct |
| 9 |
Correct |
9 ms |
8148 KB |
Output is correct |
| 10 |
Correct |
15 ms |
8508 KB |
Output is correct |
| 11 |
Correct |
13 ms |
8404 KB |
Output is correct |
| 12 |
Correct |
14 ms |
8408 KB |
Output is correct |
| 13 |
Correct |
12 ms |
8380 KB |
Output is correct |
| 14 |
Execution timed out |
10093 ms |
30624 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
