#include<bits/stdc++.h>
#define int long long
#define fr first
#define sc second
using namespace std;
const int N = 1000010;
const int p = 1e9+7;
const int q = 1e9+9;
const int b = 127;
int pot[N][2];
int potinv[N][2];
int binpow(int a, int b, int mod){
if(b == 0) return q;
int t = binpow(a, b/2, mod);
t *= t;
t %= mod;
if(b%2 == 0) return t;
else return (a*t)%mod;
}
struct hs{
pair <int, int> pref[N];
void build(string s){
pref[0] = {0, 0};
for(int i = 0;i < s.size();i++){
pref[i+1].fr = (pref[i].fr + ((s[i]-'a'+1)*pot[i][0])%p)%p;
pref[i+1].sc = (pref[i].sc+((s[i]-'a'+1)*pot[i][1])%q)%q;
}
}
pair <int, int> query(int l, int r){
l++;
r++;
return {(((pref[r].first+p-pref[l-1].first)%p)*potinv[l-1][0])%p, (((pref[r].second+q-pref[l-1].second)%q)*potinv[l-1][1])%q};
}
bool get(int l1, int r1, int l2, int r2){
if(query(l1, r1) == query(l2, r2)) return true;
return false;
}
} h;
int res[N];
void solve(){
string s;
cin >> s;
h.build(s);
int n = s.size();
if(n == 1){
cout << 1 << '\n';
return;
}
int st = (n%2 == 0 ? (n-1)/2 : n/2);
res[st+1] = 0;
res[st] = (n%2 == 1 ? 1 : (s[st] == s[st+1] ? 2 : 1));
for(int i = st-1;i >= 0;i--){
int r = (n%2 == 1 ? st+st-i : st+st-i+1);
//cout << i << ' ' << r << '\n';
res[i] = 1;
for(int j = i;j <= st;j++){
// cout << i << ' ' << j << ' ' << r-(j-i) << ' ' << r << ' ' << h.get(i, j, r-(j-i), r) << '\n';
if(h.get(i, j, r-(j-i), r)){
res[i] = max(res[i], res[j+1]+2);
}
}
}
cout << res[0] << '\n';
}
int32_t main(){
ios::sync_with_stdio(false); cin.tie(0);
int t;
cin >> t;
pot[0][0] = pot[0][1] = 1;
potinv[0][0] = potinv[0][1] = 1;
for(int i = 1;i < N;i++){
pot[i][0] = (pot[i-1][0]*b)%p;
pot[i][1] = (pot[i-1][1]*b)%q;
potinv[i][0] = binpow(pot[i][0], p-2, p);
potinv[i][1] = binpow(pot[i][1], q-2, q);
}
while(t--){
solve();
}
return 0;
}
Compilation message
palindromic.cpp: In member function 'void hs::build(std::string)':
palindromic.cpp:28:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for(int i = 0;i < s.size();i++){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
417 ms |
34516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
417 ms |
34516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
417 ms |
34516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
417 ms |
34516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
