Pagini recente » Cod sursa (job #3257813) | Cod sursa (job #2975966) | Cod sursa (job #2473195) | Cod sursa (job #3151888) | Cod sursa (job #3272664)
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
const int Nmax=1e6+5;
int p[Nmax];
signed main()
{
string s;
fin>>s;
vector<char> t;
for(auto ch:s)
{
t.push_back('#');
t.push_back(ch);
}
t.push_back('#');
int n=t.size()-2;
int sol=0;
int l=1,r=1;
for(int i=1;i<=n;i++)
{
p[i]=max(0LL,min(r-i,p[l+(r-i)]));
while(i-p[i]>=0 && i+p[i]<=n+1 && t[i-p[i]]==t[i+p[i]])
{
p[i]++;
}
sol+=(p[i])/2;
if(i+p[i]>r)
{
r=i+p[i],l=i-p[i];
}
}
fout<<sol<<'\n';
return 0;
}