#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define forin(i , a , b ) for (int i = (a) ; i <= (b) ; i ++)
#define pb push_back
const int maxn = 1e6 + 100 ;
const int mod1 = 1e9 + 7 ;
const int mod2 = 1e6 + 7 ;
string s ;
int a[maxn] ,hashA[maxn] , Pow1[maxn];
int hashB[maxn] , Pow2[maxn];
long long getHashA(int i, int j)
{
return ((hashA[j] - hashA[i-1] * Pow1[j-i+1]) % mod1 + mod1) % mod1;
}
long long getHashB(int i, int j)
{
return ((hashB[j] - hashB[i-1] * Pow2[j-i+1]) % mod2 + mod2) % mod2;
}
signed main ()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int tt;
cin >> tt;
while (tt--)
{
string s;
cin >> s ;
s = '!' + s ;
int n = s.size() - 1 ;
forin(i , 1 , n)
a[i] = s[i] - 'a' + 1;
Pow1[0] = Pow2[0] = 1;
forin (i , 1 , n) Pow1[i] = (Pow1[i-1] * 300) % mod1;
forin (i , 1 , n) Pow2[i] = (Pow2[i-1] * 300) % mod2;
hashA[0] = hashB[0] = 0;
forin (i, 1 , n) hashA[i] = (hashA[i-1] * 300 + a[i]) % mod1;
forin (i, 1 , n) hashB[i] = (hashB[i-1] * 300 + a[i]) % mod2;
int l = 1 , r = 1 , x = n , y = n ;
int ans = 0 ;
while (true)
{
if (r == x || r > x)
{
ans ++ ;
break ;
}
if (getHashA(l , r) == getHashA(x,y) && getHashB(l , r) == getHashB(x,y))
{
ans+=2;
r ++;
l = r ;
x --;
y = x ;
}
else
{
r++;
x--;
}
}
cout << ans << "\n";
forin(i,1,n) Pow1[i] = hashA[i] = hashB[i] = Pow2[i] = a[i] = 0 ;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
10588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
10588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
10588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
10588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
