#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int MAXN = 1000010;
int prime = 31;
int mod = 1000000009;
int n;
lli pot[MAXN];
lli pHash[MAXN];
string s;
int getHash(int L, int R)
{
lli ans = pHash[R + 1];
ans -= pHash[L]*pot[R - L + 1];
ans %= mod;
if( ans < 0 ) ans += mod;
return (int)ans;
}
int main()
{
int t;
cin >> t;
pot[0] = 1;
for(int i = 1 ; i < MAXN ; i++)
pot[i] = pot[i - 1]*prime, pot[i] %= mod;
while( t-- )
{
cin >> s;
n = (int)s.size();
for(int i = 1 ; i <= n ; i++)
{
pHash[i] = pHash[i - 1]*prime + s[i - 1] - 'a';
pHash[i] %= mod;
}
int sz = 1, ans = 0;
int l = 0, r = n - 1;
while( l <= r )
{
sz = 1;
while( getHash( l , l + sz - 1 ) != getHash( r - sz + 1 , r ) )
sz++;
ans++;
l += sz; r -= sz;
if( l <= r + 1 ) ans++;
}
printf("%d\n",ans);
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
8192 KB |
Output is correct |
| 2 |
Correct |
14 ms |
8192 KB |
Output is correct |
| 3 |
Correct |
15 ms |
8192 KB |
Output is correct |
| 4 |
Correct |
13 ms |
8192 KB |
Output is correct |
| 5 |
Correct |
13 ms |
8192 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
8192 KB |
Output is correct |
| 2 |
Correct |
14 ms |
8192 KB |
Output is correct |
| 3 |
Correct |
15 ms |
8192 KB |
Output is correct |
| 4 |
Correct |
13 ms |
8192 KB |
Output is correct |
| 5 |
Correct |
13 ms |
8192 KB |
Output is correct |
| 6 |
Correct |
15 ms |
8192 KB |
Output is correct |
| 7 |
Correct |
15 ms |
8192 KB |
Output is correct |
| 8 |
Correct |
14 ms |
8192 KB |
Output is correct |
| 9 |
Correct |
14 ms |
8192 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
8192 KB |
Output is correct |
| 2 |
Correct |
14 ms |
8192 KB |
Output is correct |
| 3 |
Correct |
15 ms |
8192 KB |
Output is correct |
| 4 |
Correct |
13 ms |
8192 KB |
Output is correct |
| 5 |
Correct |
13 ms |
8192 KB |
Output is correct |
| 6 |
Correct |
15 ms |
8192 KB |
Output is correct |
| 7 |
Correct |
15 ms |
8192 KB |
Output is correct |
| 8 |
Correct |
14 ms |
8192 KB |
Output is correct |
| 9 |
Correct |
14 ms |
8192 KB |
Output is correct |
| 10 |
Correct |
21 ms |
8192 KB |
Output is correct |
| 11 |
Correct |
18 ms |
8192 KB |
Output is correct |
| 12 |
Correct |
20 ms |
8192 KB |
Output is correct |
| 13 |
Correct |
18 ms |
8192 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
15 ms |
8192 KB |
Output is correct |
| 2 |
Correct |
14 ms |
8192 KB |
Output is correct |
| 3 |
Correct |
15 ms |
8192 KB |
Output is correct |
| 4 |
Correct |
13 ms |
8192 KB |
Output is correct |
| 5 |
Correct |
13 ms |
8192 KB |
Output is correct |
| 6 |
Correct |
15 ms |
8192 KB |
Output is correct |
| 7 |
Correct |
15 ms |
8192 KB |
Output is correct |
| 8 |
Correct |
14 ms |
8192 KB |
Output is correct |
| 9 |
Correct |
14 ms |
8192 KB |
Output is correct |
| 10 |
Correct |
21 ms |
8192 KB |
Output is correct |
| 11 |
Correct |
18 ms |
8192 KB |
Output is correct |
| 12 |
Correct |
20 ms |
8192 KB |
Output is correct |
| 13 |
Correct |
18 ms |
8192 KB |
Output is correct |
| 14 |
Correct |
644 ms |
17160 KB |
Output is correct |
| 15 |
Correct |
355 ms |
17840 KB |
Output is correct |
| 16 |
Correct |
632 ms |
17840 KB |
Output is correct |
| 17 |
Correct |
342 ms |
13008 KB |
Output is correct |
