This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int P = 31;
const int M = 1e9+9;
vector<int> binpow;
vector<int> pref;
int gethash(int l, int r){
int h = ((pref[r+1] - (binpow[r-l+1] * pref[l]))%M + M)%M;
return h;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--){
string s;
cin >> s;
int n = s.size();
binpow.clear();
binpow.resize(n);
binpow[0] = 1;
for (int i = 1; i<n; i++){
binpow[i] = (binpow[i-1]*P) % M;
}
pref.clear();
pref.resize(n+1);
pref[0] = 0;
for (int i = 1; i<=n; i++){
pref[i] = ((pref[i-1]*P)+(s[i-1]-'a'+1)) % M;
}
int r = 0;
int ln = 0;
int ans = 0;
vector<bool> vis(n);
int lst = n-1;
while (r+ln < n/2){
int st = r; int stt = r+ln;
int nd = lst-ln; int ndd = lst;
int one = gethash(st,stt);
int two = gethash(nd,ndd);
//cout << st << " " << stt << " " << nd << " " << ndd << "\n";
//cout << one << " " << two << "\n\n";
if (one == two){
for (int i = st; i<=stt; i++){
vis[i] = true;
}
for (int i = nd; i<=ndd; i++){
vis[i] = true;
}
ans += 2;
r += ln+1;
lst -= ln+1;
ln = 0;
}
else{
ln++;
}
}
int bk = 0;
for (int i = 0; i<n; i++){
bk += vis[i];
}
if (bk != n) ans++;
cout << ans << '\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |