Pagini recente » Cod sursa (job #3333122) | Cod sursa (job #3315968) | Cod sursa (job #3329798) | Cod sursa (job #3318963) | Cod sursa (job #3329600)
#include <fstream>
#include <map>
#include <vector>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <deque>
#include <math.h>
#include <queue>
#include <set>
#pragma GCC optimize ("Ofast","unroll-loops")
#pragma GCC target ("sse")
using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
const int maxn=2e6+10;
int manacher[maxn];
void build_manacher(const string a) {
int best=1;
int n=a.size();
for (int i=1;i<n;i++) {
int simetric=best-(i-best);
manacher[i]=min(manacher[simetric]+i,manacher[best]+best)-i;
while (a[i+manacher[i]+1]==a[i-manacher[i]-1]) manacher[i]++;
if (manacher[best]+best<manacher[i]+i)best=i;
}
}
void solve(){
string s1;
cin>>s1;
string s;
s="##";
for (auto elem:s1) {
s.push_back(elem);
s.push_back('#');
}
build_manacher(s);
int rsp=0;
for (int i=0;i<s.size();i++) {
rsp+=(manacher[i]+1)/2;
}
cout<<rsp;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
t=1;
while(t--)solve();
return 0;
}