#pragma GCC optimize("O2")
#include<bits/stdc++.h>
typedef long long ll ;
#define pll pair<ll , ll >
#define X first
#define Y second
#define mp make_pair
#define pii pair<int , int>
#define vec vector
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
using namespace std;
const int maxn = 1000*1000+5 ;
const ll inf = 9223372036854775807 ;
const ll mod = 1000696969 ;
const ll mod2 = 1e9 + 7 ;
const ll H = 1777013 ;
string s ;
ll pt[maxn] , h[maxn] , L , R , sz , n , l, r , mid , b , ans ;
ll hsh(int l , int r){
if(l == 0 ) return h[r] ;
return ( h[r] - h[l-1] * pt[r-l+1] % mod + mod ) % mod ; }
bool check(int x){
return( hsh(L , L + x - 1) == hsh(R - x + 1 , R) ) ;
}
int Main()
{
ans = 0 ;
cin>>s ; n = s.size() ;
h[0] = s[0] ;
for(int i = 1 ; i < n ; i ++ ){
h[i] = h[i-1] * H % mod + s[i] ;
h[i] %= mod ;
}
L= 0 , R = n - 1 ;
while(n > 0){
l = 1 , r = n/2 + 1 , b = 1 ;
if(r-l == 0){
n = 0 ;
ans ++ ;
break ;
}
while(r-l>1){
mid = (l + r)/ 2 ;
if(check(mid)) l = mid , b = 0 ;
else r = mid ;
}
if(!check(l)){
n = 0 ;
ans ++ ;
}else{
L += l ;
R -= l ;
ans += 2 ;
n -= 2 * l ;
// cout<<ans << " " << l <<" " << L <<" " << R <<" " << n << endl ;
}
}
cout<<ans << endl ;
return 0 ;
}
int main()
{
int t ;
migmig;
pt[0] = 1 ;
for(int i = 1; i < maxn ; i ++ )
{
pt[i] = pt[i-1] * H % mod ;
}
cin>> t ;
while(t--)
{
Main() ;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
8172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
8172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
8172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
8172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
