#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define Abdoo ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
void pr(vector<int> v) {
for (int i = 0; i < v.size(); ++i) {
cout << v[i] << " ";
}
cout << "\n";
}
const int N = 1e6 +5, MOD = 1e9 + 9;
ll pw[N], inv[N], pref[N], p = 31;
ll add(ll a,ll b){
return (a+b) % MOD;
}
ll mul(ll a,ll b){
return 1ll * (a * b)%MOD;
}
ll sub(ll a, ll b){
return ((a-b) % MOD + MOD) % MOD;
}
ll fast_power(ll b, ll p){
ll ans = 1;
while(p){
if(p&1) ans = mul(ans, b);
b = mul(b, b);
p /= 2;
}
return ans;
}
void pre(){
pw[0] = inv[0] = 1;
ll inverse = fast_power(p, MOD - 2);
for(int i = 1; i < N; i++){
pw[i] = mul(pw[i-1] , p);
inv[i] = mul(inv[i-1], inverse);
}
}
ll getHash(int l, int r){
l++,r++;
return mul(add(pref[r],MOD - pref[l-1]), inv[l-1]);
}
void generateHash(string &s){
for (int i = 1; i <= s.size(); ++i) {
int idx = s[i-1]-'a'+1;
pref[i] = mul(idx, pw[i-1]);
pref[i] = add(pref[i],pref[i-1]);
}
}
int main() {
Abdoo
pre();
int tc = 1;
cin >> tc;
while (tc--) {
string s;
cin >> s;
generateHash(s);
int st = 0, en = s.size()- 1, ans = 0;
while(st < en){
int st2 = st, en2 = en;
while(st2 < en2 && getHash(st, st2) != getHash(en2, en)){
st2++, en2--;
}
if(st2 < en2 &&getHash(st, st2) == getHash(en2, en)){
//cout << st << " " << st2 << " " << en2 << " " << en << "\n";
ans += 2;
}
st = st2, en = en2;
st++, en--;
}
ans++;
cout << ans << "\n";
}
return 0;
}
Compilation message
palindromic.cpp: In function 'void pr(std::vector<int>)':
palindromic.cpp:10:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
10 | for (int i = 0; i < v.size(); ++i) {
| ~~^~~~~~~~~~
palindromic.cpp: In function 'void generateHash(std::string&)':
palindromic.cpp:52:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for (int i = 1; i <= s.size(); ++i) {
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
17612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
17612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
17612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
17612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
