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>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int nax=1e6+5;
const int MOD=1e9+9;
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
vector<ll> pw={1};
vector<ll> p_hash(nax);
long long B=9973;
void compute_hash(string s){
while(pw.size()<s.size()){
pw.pb((pw.back()*B)%MOD);
}
p_hash[0]=0;
for (int i = 0; i < s.size(); ++i)
{
p_hash[i+1]=((p_hash[i]*B)%MOD+s[i])%MOD;
}
return;
}
int get_hash(int l,int r){
long long ans=(p_hash[r+1]-(p_hash[l]*pw[r-l+1]));
return (ans%MOD + MOD)%MOD;
}
int main()
{
optimise;
int test_cases;
cin>>test_cases;
while(test_cases--){
string t;
cin>>t;
int n=t.size()+1;
reverse(t.begin(),t.end());
t.pb(' ');
reverse(t.begin(),t.end());
compute_hash(t);
int ans=0;
int lst=1;
bool test=false;
for (int i = 1; i <= n/2; ++i)
{
if(get_hash(lst,i)==get_hash(n-i,n-lst)){
ans+=2;
if(i==n/2&&n%2==0&&i==lst) ans--;
lst=i+1;
}else if(i==n/2) ans++;
}
cout <<ans<<endl;
}
}
Compilation message (stderr)
palindromic.cpp: In function 'void compute_hash(std::string)':
palindromic.cpp:25:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for (int i = 0; i < s.size(); ++i)
| ~~^~~~~~~~~~
palindromic.cpp: In function 'int main()':
palindromic.cpp:50:14: warning: unused variable 'test' [-Wunused-variable]
50 | bool test=false;
| ^~~~
# | 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... |