#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
typedef long long ll;
ll hash1[MAXN], hash2[MAXN];
ll pp1[MAXN], pp2[MAXN];
ll p1, p2;
pair<ll, ll> subhash(int i, int j){
return make_pair(hash1[i] - (j ? hash1[j - 1] * pp1[i - j + 1] : 0),
hash2[i] - (j ? hash2[j - 1] * pp2[i - j + 1] : 0));
}
string s;
int n;
void resetandin(){
cin >> s;
n = s.length();
hash1[0] = hash2[0] = s[0];
for(int i = 1; i < n; i ++){
hash1[i] *= p1;
hash1[i] += s[i];
hash2[i] *= p2;
hash2[i] += s[i];
}
}
int main(){
pp1[0] = pp2[0] = 1;
for(int i = 1; i < MAXN; i++){
pp1[i] = pp1[i-1] * p1;
pp2[i] = pp2[i-1] * p2;
}
int t;
cin >> t;
while(t--){
resetandin();
int ans = 0;
int esq = 0, dir = n - 1;
for(int i = 0; i < n/2; i++){
// esq.push_back(s[i]);
// dir = (s[s.length()-i-1]) + dir;
if(subhash(i, esq) == subhash(dir, n - i - 1)){
esq = i+1;
dir = n - i - 2;
ans+=2;
}
}
if(s.length()%2 ||esq < n/2)ans++;
cout << ans << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
16000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
16000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
16000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
16000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
