#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 1000100;
const ll MOD = 1e9+9;
string s;
int n;
ll hsh[N], st[N];
ll gethsh(int l, int r){
return (hsh[r]-hsh[l-1]+MOD)*st[n-r]%MOD;
}
void solve(){
st[0] = 1;
cin >> s;
n = s.size();
s = '#' + s;
for (int i = 1; i <= n; i++){
st[i] = (st[i-1] * 43) % MOD;
hsh[i] = (hsh[i-1] + st[i]*s[i])%MOD;
}
int i = 1;
int j = n;
int sz = 1;
int ans = 0;
while(1){
if (i+sz-1 >= j-sz+1){
++ans;
break;
}
if (gethsh(i, i+sz-1) == gethsh(j-sz+1, j)){
ans += 2;
i += sz;
j -= sz;
sz = 1;
if (i-1 == j)
break;
continue;
}
++sz;
}
cout << ans << "\n";
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int tt;
cin >> tt;
while(tt--){
solve();
}
}
/**
1
deleted
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
3 ms |
640 KB |
Output is correct |
11 |
Correct |
3 ms |
640 KB |
Output is correct |
12 |
Correct |
3 ms |
640 KB |
Output is correct |
13 |
Correct |
3 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
3 ms |
640 KB |
Output is correct |
11 |
Correct |
3 ms |
640 KB |
Output is correct |
12 |
Correct |
3 ms |
640 KB |
Output is correct |
13 |
Correct |
3 ms |
640 KB |
Output is correct |
14 |
Correct |
139 ms |
27756 KB |
Output is correct |
15 |
Correct |
83 ms |
22968 KB |
Output is correct |
16 |
Correct |
155 ms |
28960 KB |
Output is correct |
17 |
Correct |
77 ms |
14752 KB |
Output is correct |