#include <bits/stdc++.h>
// #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
#define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ss second
#define ff first
void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 1e5 + 1, maxk = 101, lg = 21, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}
struct PolyHash{
#define __cnt 2
ll mod[__cnt] = {998244353, ll(1e9) + 7}, p = 9973;
vector<ll> pw[__cnt], hsh[__cnt];
PolyHash(){
rep(i,0,__cnt) pw[i].pb(1);
}
PolyHash(vector<int> a){
int n = sz(a);
rep(i,0,__cnt){
pw[i].assign(n + 1, 1);
rep(j,1,n + 1) pw[i][j] = p*pw[i][j-1]%mod[i];
hsh[i].assign(n, a[0]);
rep(j,1,n) hsh[i][j] = p*hsh[i][j-1]%mod[i] + a[j], hsh[i][j] %= mod[i];
}
}
void add(int k){
rep(i,0,__cnt){
pw[i].pb(pw[i].back()*p%mod[i]);
hsh[i].pb(((sz(hsh[i])?hsh[i].back():0)*p%mod[i] + k)%mod[i]);
}
}
int get(int l, int r, int id = 0){
return (hsh[id][r] - (l?hsh[id][l-1]:0)*pw[id][r - l + 1]%mod[id] + mod[id])%mod[id];
}
int get(int id = 0){ return get(0, sz(hsh[id])-1, id); }
pp get2(int l, int r){
return {get(l, r, 0), get(l, r, 1)};
}
pp get2(){ return get2(0, sz(hsh[0])-1); }
vector<int> get_mul(int l, int r){
vector<int> res;
rep(i,0,__cnt) res.pb(get(l, r, i));
return res;
}
vector<int> get_mul(){ return get_mul(0, sz(hsh[0])-1); }
};
void solve(){
string s; cin >> s; int n = sz(s);
vector<int> a(n), b;
rep(i,0,n) a[i] = s[i] - 'a';
b = a, reverse(all(b));
PolyHash hsh(a);
int cr = 0, ans = 0;
while(true){
bool ok = false;
rep(i,cr,n>>1) if(hsh.get(cr, i) == hsh.get(n-1-i, n-1-cr)){
ok = true, cr = i + 1, ans++;
break;
}
if(!ok || cr >= ((n+1)>>1)) break;
}
ans <<= 1;
if(cr < ((n+1)>>1) ) ans++;
cout << ans << '\n';
}
int main(){
cin.tie(0) -> sync_with_stdio(0);
int t; cin >> t;
while(t--) solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
324 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
324 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
324 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
324 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
324 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
9 ms |
912 KB |
Output is correct |
11 |
Correct |
4 ms |
816 KB |
Output is correct |
12 |
Correct |
8 ms |
840 KB |
Output is correct |
13 |
Correct |
7 ms |
796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
324 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
324 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
9 ms |
912 KB |
Output is correct |
11 |
Correct |
4 ms |
816 KB |
Output is correct |
12 |
Correct |
8 ms |
840 KB |
Output is correct |
13 |
Correct |
7 ms |
796 KB |
Output is correct |
14 |
Correct |
764 ms |
55184 KB |
Output is correct |
15 |
Correct |
402 ms |
49852 KB |
Output is correct |
16 |
Correct |
719 ms |
51888 KB |
Output is correct |
17 |
Correct |
389 ms |
29796 KB |
Output is correct |