#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int nax=1e6+5;
const int MOD=1e9+9;
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int segtree[nax*4];
void build(int pos,int l,int r){
if(l==r){
segtree[pos]=(l==0 ? 0 : -1e9);
return;
}
int mid=(r+l)/2;
build(pos*2+1,l,mid);
build(pos*2+2,mid+1,r);
segtree[pos]=max(segtree[pos*2+1],segtree[pos*2+2]);
return;
}
void update(int pos,int l,int r,int idx,int value){
if(l==r){
segtree[pos]=value;
return;
}
int mid=(r+l)/2;
if(idx<=mid) update(pos*2+1,l,mid,idx,value);
else update(pos*2+2,mid+1,r,idx,value);
segtree[pos]=max(segtree[pos*2+1],segtree[pos*2+2]);
return;
}
int query(int pos,int l,int r,int left,int right){
if(l>r||l>right||r<left) return -1e9;
if(l>=left&&r<=right) return segtree[pos];
int mid=(r+l)/2;
return max(query(pos*2+1,l,mid,left,right),query(pos*2+2,mid+1,r,left,right));
}
vector<ll> pw={1};
vector<ll> p_hash(nax);
long long B=9973;
void compute_hash(string s){
while(pw.size()<s.size()){
pw.pb((pw.back()*B)%MOD);
}
p_hash[0]=0;
for (int i = 0; i < s.size(); ++i)
{
p_hash[i+1]=((p_hash[i]*B)%MOD+s[i])%MOD;
}
return;
}
int get_hash(int l,int r){
long long ans=(p_hash[r+1]-(p_hash[l]*pw[r-l+1]));
return (ans%MOD + MOD)%MOD;
}
int main()
{
optimise;
int test_cases;
cin>>test_cases;
while(test_cases--){
string t;
cin>>t;
int n=t.size()+1;
reverse(t.begin(),t.end());
t.pb(' ');
reverse(t.begin(),t.end());
compute_hash(t);
int dp[n];
build(0,0,n-1);
for (int i = 0; i < n; ++i)
{
dp[i]=-1e9;
}
dp[0]=0;
int ans=1;
for (int i = 1; i <= n/2; ++i)
{
int l=-1;
int r=i+1;
while(r-l>1){
int mid=(r+l)/2;
if(get_hash(mid,i)==get_hash(n-i,n-mid)){
r=mid;
}else l=mid;
}
if(r==i+1) continue;
dp[i]=query(0,0,n-1,r-1,i)+1;
update(0,0,n-1,i,dp[i]);
ans=max(ans,(dp[i]*2-((i==n/2&&(n%2==0||t[i]!=t[n-i]) ? 1 : 0))+(i==n/2 ? 0 : 1)));
}cout <<ans<<endl;
}
}
Compilation message
palindromic.cpp: In function 'void compute_hash(std::string)':
palindromic.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for (int i = 0; i < s.size(); ++i)
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
8280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
8280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
8280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
8280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
