| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 627074 | 2022-08-12T06:36:31 Z | a_aguilo | Palindromic Partitions (CEOI17_palindromic) | C++17 | 0 ms | 0 KB |
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int p = 73;
const long long m = 1e11 + 3;
long long int hashes[1000000];
long long int powers[1000000];
int n;
long long getHash(int start, int ending){
if(ending == 0) return hashes[0];
if(start == n-1) return ((hashes[n-1] - (hashes[n - 2] * p)%m)%m + m)%m;
if(start == 0) return hashes[ending];
return ((hashes[ending] - (hashes[start - 1] * powers[ending - start+1])%m)%m + m)%m;
}
int main(){
int t;
string s;
cin >> t;
while(t--){
cin >> s;
n = s.size();
memset(hashes, 0, sizeof(hashes));
memset(powers, 0, sizeof(powers));
hashes[0] = s[0]-'a'+1;
powers[0] = 1;
for(int i = 1; i < s.size(); ++i){
hashes[i] = (((__int128)hashes[i-1]*p)%m + (s[i]-'a' + 1))%m;
powers[i] = ((__int128)powers[i-1]*p)%m;
}
int ans = 1;
int MaxLeft = -1;
int MaxRight = s.size();
int left = 0; int right = s.size()-1;
while(left < right){
if(getHash(MaxLeft+1, left) == getHash(right, MaxRight-1)){
ans+=2;
MaxLeft = left;
MaxRight = right;
}
left++;
right--;
}
if(MaxLeft+1 == MaxRight)ans--;
cout << ans << endl;;
}
return 0;
}