#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9+7,P=47,mx=1e6+5;
ll h[mx],p[mx];
string s;
bool check(ll a,ll b,ll l) {
if(a>b) return false;
ll h1=h[a+l-1]-h[a-1];
ll h2=h[b+l-1]-h[b-1];
return (1LL*h1*p[b-a])%mod == h2;
}
void solve() {
cin >> s;
ll n=ll(s.size());
for(ll i=1;i<=n;++i) {
h[i]=(h[i-1]+(s[i-1]-'a'+1)*p[i-1])%mod;
h[i]%=mod;
}
ll l=1,r=n,res=0;
while(l<=r) {
ll k=1;
while(!check(l,r-k+1,k)) {
++k;
}
l+=k,r-=k;
res+=2;
}
cout << res-1;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
p[0]=1;
for(int i=1;i<mx;++i) {
p[i]=(p[i-1]*P)%mod;
}
ll t; cin >> t;
while(t--) {
solve();
cout << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
8796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
8796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
8796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
8796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
