#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#include "/Users/quocbaonguyentran/Documents/VOI25/template/debug.cpp"
#else
#define debug(...) ;
#endif
using namespace std;
#define endl "\n"
#define ll long long
#define ull uint64_t
#define uint uint32_t
const int N = 1e6;
const ull mod = (1ull << 61) - 1;
const ull seed = chrono::system_clock::now().time_since_epoch().count();
const ull base = mt19937_64(seed)() % (mod / 3) + (mod / 3);
ull Pow[N + 5];
ll modmul(ull a, ull b)
{
ull l1 = (uint)a;
ull h1 = a >> 32;
ull l2 = (uint)b;
ull h2 = b >> 32;
ull l = l1 * l2;
ull m = l1 * h2 + l2 * h1;
ull h = h1 * h2;
ull res = (l & mod) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
res = (res & mod) + (res >> 61);
res = (res & mod) + (res >> 61);
return res - 1;
}
void init()
{
Pow[0] = 1;
for (int i = 1; i <= N; i++)
{
Pow[i] = modmul(Pow[i - 1], base);
}
}
struct Hashing
{
vector<ll> pre, suf;
Hashing() {}
template <typename T>
Hashing(const vector<T> &a)
{
if (Pow[0] == 0)
init();
int n = a.size();
pre = suf = vector<ll>(n + 5, 0);
for (int i = 1; i <= n; i++)
{
pre[i] = modmul(pre[i - 1], base) + a[i - 1] + 977;
if (pre[i] >= mod)
pre[i] -= mod;
}
for (int i = n; i >= 1; i--)
{
suf[i] = modmul(suf[i + 1], base) + a[i - 1] + 977;
if (suf[i] >= mod)
suf[i] -= mod;
}
}
Hashing(const char *str)
: Hashing(vector<char>(str, str + strlen(str))) {}
Hashing(const string &str)
: Hashing(vector<char>(str.begin(), str.end())) {}
ull get_hash(int l, int r)
{
ll h = pre[r] - modmul(Pow[r - l + 1], pre[l - 1]);
return h < 0 ? h + mod : h;
}
ull rev_hash(int l, int r)
{
ll h = suf[l] - modmul(Pow[r - l + 1], suf[r + 1]);
return h < 0 ? h + mod : h;
}
};
int t;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> t;
while (t--)
{
string s;
cin >> s;
Hashing t(s);
int n = s.size();
int l = 1, r = n;
int le = 1, ri = n;
int dem = 0;
while (l < r)
{
// debug(le, l, ri, r);
if (t.get_hash(le, l) == t.get_hash(r, ri))
{
dem++;
le = l + 1;
ri = r - 1;
}
l++;
r--;
}
// debug(le, l, ri, r);
dem *= 2;
if (le <= ri) dem++;
cout << dem << endl;
}
}
/*
4
bonobo
deleted
racecar
racecars
*/
Compilation message
palindromic.cpp:3:10: fatal error: /Users/quocbaonguyentran/Documents/VOI25/template/debug.cpp: No such file or directory
3 | #include "/Users/quocbaonguyentran/Documents/VOI25/template/debug.cpp"
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
compilation terminated.
