#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair
#define S second
#define F first
#define all(v) v.begin(),v.end()
#define V vector
#define pb push_back
const ll MOD=998244353;
struct segtree{
private:
struct node{
ll ans;
ll l;
ll maxl_1;
ll maxl_2;
ll maxr_1;
ll maxr_2;
};
node merge(node a,node b){
if(a.maxl_1==LLONG_MIN)
return b;
if(b.maxl_1==LLONG_MIN)
return a;
static node c;
c.l=a.l+b.l;
c.ans=max(max(a.ans,b.ans),max(b.maxl_1+a.maxr_2-1,b.maxl_2+a.maxr_1-1));
c.maxl_1=max(a.maxl_1,b.maxl_1-a.l);
c.maxl_2=max(a.maxl_2,b.maxl_2-a.l);
c.maxr_1=max(b.maxr_1,a.maxr_1-b.l);
c.maxr_2=max(b.maxr_2,a.maxr_2-b.l);
return c;
}
node neutral{0,0,LLONG_MIN};
node single(ll a){
return{0,1,a,-a,a,-a};
}
public:
V<node>query;
int size;
void init(int n){
size=1;
while(size<n){
size*=2;
}
query.resize(2*size);
}
void build(V<int>&a,int x,int lx,int rx){
if(rx-lx==1){
if(lx<(int)a.size()){
query[x]=single(a[lx]);
}
return;
}
int m=(lx+rx)/2;
build(a,2*x+1,lx,m);
build(a,2*x+2,m,rx);
query[x]=merge(query[2*x+1],query[2*x+2]);
}
void build(V<int>&a){
build(a,0,0,size);
}
void update(int i,int v,int x,int lx,int rx){
if(rx-lx==1){
query[x]=single(v);
return;
}
int m=(lx+rx)/2;
if(i<m)
update(i,v,2*x+1,lx,m);
else
update(i,v,2*x+2,m,rx);
}
void update(int i,int v){
update(i,v,0,0,size);
}
node calc(int l,int r,int x,int lx,int rx) {
if (r <= lx || rx >= l)
return neutral;
if (lx >= l && rx <= r)
return query[x];
int m = (lx + rx) / 2;
node a = calc(l, r, 2 * x + 1, lx, m);
node b = calc(l, r, 2 * x + 2, m, rx);
return merge(a, b);
}
};
void file() {
freopen("input.txt.txt", "r", stdin);
freopen("output.txt.txt", "w", stdout);
}
bool check(string &t1,string t2) {
reverse(all(t2));
return t1 == t2;
}
string s; int ans;
void search(int i, int j){
string a="", b="";
if(j-i==0){
ans++;
return;
}
if(j-i<0)
return;
while(i < j){
a += s[i], b += s[j];
reverse(all(b));
if (a == b) {
ans+=2;
search(i+1, j-1);
return;
}
else {
reverse(all(b));
i++;
j--;
}
}
ans++;
}
void solve() {
cin>>s;
int n=(int)s.length();
ans=0;
search(0,n-1);
cout<<ans<<endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//file();
int t;
cin>>t;
while(t--) {
solve();
}
}
Compilation message (stderr)
palindromic.cpp: In function 'void file()':
palindromic.cpp:90:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
90 | freopen("input.txt.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
palindromic.cpp:91:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
91 | freopen("output.txt.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |