#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define int long long
const int mod = 1e9 + 7;
const int p = 31;
const int N = 2e5;
/*
4
bonobo
deleted
racecar
racecars
*/
int pw[N+10];
void solve(){
string s; cin >> s;
int n = s.size();
vector<int> hash(n, 0);
hash[0] = s[0];
for(int i = 1;i < n; i++){
hash[i] = (hash[i-1] * p + s[i]) % mod;
}
auto get=[&](int l, int r){
if(l == 0) return hash[r];
int sum = hash[r] - (pw[r-l+1] * hash[l-1]);
sum = ((sum % mod) + mod) % mod;
return sum;
};
deque<char> dq;
for(int i = 0;i < n; i++) dq.push_back(s[i]);
int left = 0, right = n-1;
int ans = 0;
while(true){
int len = -1;
for(int j = right; j >= 0; j--){
if(left + right - j >= j) break;
/*cout << j+1 << " " << right + 1 << '\n';
cout << left + 1 << ' ' << left + right - j + 1 << "\n";
cout << get(j, right) << ' ' << get(left, left+(right-j)) << '\n';
* */
if(get(j, right) == get(left, left+(right-j))){
len = (right-j+1);
break;
}
}
if(len == -1){
ans++;
break;
}
ans+= 2;
if(dq.empty()) break;
left+= len, right-= len;
}
cout << ans;
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
pw[0] = 1;
for(int i = 1;i <= N; i++){
pw[i] = (pw[i-1] * p) % mod;
}
int tt; cin >> tt;
while(tt--){
solve();
cout << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
