This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
///* __ __ __ */
///* ====== _ /| /| __ _ / | | /| | @ | | | | / /| |\ | / | | @ | / */
///* \- || |_| |_ / |/ | | | |_ |- | |--| /-| | | \ \ |==| |- /=| | \ | | |--| | |- */
///* || | | |_ / | |__| _| |_ \__ | | / | |__ | __| | | | \ / | | \| \__ | | | | \ */
///*
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define int long long
typedef vector<int> vi;
typedef vector<double> vd;
typedef pair<int,int> pii;
typedef vector<pii> vii;
const int N = 3e5+50, inf = 1e18, mod = 1e9+7;
void solve(){
string s;
cin >> s;
int n = s.size(), ans = 0;
map<char, vi> mp;
for(int i = n/2; i < n; i++){
mp[s[i]].pb(i);
}
int l = 0, r = n;
while(l < r){
while(mp[s[l]].size() > 0 && mp[s[l]].back() >= r){
mp[s[l]].pop_back();
}
bool ok = 0;
for(int i = mp[s[l]].size()-1; i >= 0; i--){
int x = mp[s[l]][i];
int len = r-x;
bool eq = 1;
for(int it1 = l, it2 = x; it2 < x+len; it1++,it2++){
if(s[it1] != s[it2]){
eq = 0;break;
}
}
if(eq){
ok = 1;
ans += 2;
ans -= (x == l);
l += len;
r -= len;
break;
}
}
//cout << l << ' ' << r << '\n';
if(!ok){
ans++;
break;
}
}
cout << ans << '\n';
}
main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int test = 1;
cin >> test;
while(test--){
solve();
}
}
Compilation message (stderr)
palindromic.cpp:60:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
60 | main(){
| ^~~~
# | 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... |