/*
#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma,tune=native")
//*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int ,int > pii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll maxn = 3e6;
const ll mod =1e9+7;
const ll mods [] = {(ll)1e9+7 , (ll)1e9+9 , 696969569 , 177013 , 9699691};
const ld PI = acos((ld)-1);
#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}
struct hsh{
string s;
ll n;
vector < ll > h;
vector < ll > p;
ll base;
ll mod;
hsh (string S){
s = S;
n = s.size();
h.reserve(n+100);
base = rng()%100 + 50;
mod = mods[rng()%5];
p.pb(1);
for(int i = 1 ; i < n + 50 ; i ++)
p.pb((p.back() * base)%mod);
}
void calc(){
ll cur = 0;
h.pb(cur);
for(int i = 0 ; i < n ; i ++){
cur = (cur * base)%mod;
cur += s[i] - 'a' + 1;
cur%=mod;
h.pb(cur);
}
}
ll get(ll l , ll r){
ll res = h[r];
res -= (h[l-1]*p[r-l+1])%mod;
res%=mod;
res+=mod;
return(res%mod);
}
};
int t;
string s;
int32_t main(){
migmig;
cin >> t;
while(t -- ){
cin >> s;
hsh h(s);
h.calc();
int n = s.size();
int l = 1 , r = n ;
int ans = 0;
while (l!=r){
bool ok = 0;
for(int i = l ; i < r ; i ++){
if(i >= r-i+l)
break;
if(h.get(l , i) == h.get(r - i+l , r)){
ans += 2;
r = r - i + l-1;
l = i+1;
ok = 1;
break;
}
}
if(!ok or (ok and l == r))
ans ++ , l = r;
}
if(ans==0)ans++;
cout << ans << endl;
}
return(0);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
