Pagini recente » Cod sursa (job #186029) | Cod sursa (job #2837248) | Cod sursa (job #2573750) | Cod sursa (job #252808) | Cod sursa (job #2586192)
///pscpld
#include <bits/stdc++.h>
using namespace std;
const int N=1000005;
string s;
int p[2*N];
void dffs(int node)
{
for(int i=1;i<=node;++i)
if(i^(i&-i))
dffs(i);
}
string getmform(string s)
{
string rez="!#";
for(int i=0; i<s.size(); i++)
{
rez+=s[i];
rez+="#";
}
rez+="$";
return rez;
}
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
int main()
{
fin>>s;
s=getmform(s);
int c=0,r=0;
for(int i=1; i<s.size()-1; i++)
{
int rad=0;
if(i<=r)
{
rad=min(r-i+1,p[c-(i-c)]);
}
while(s[i+rad+1]==s[i-rad-1])
rad++;
p[i]=rad;
if(i+p[i]-1>r)
{
c=i;
r=i+p[i]-1;
}
}
long long ans=0;
for(int i=1; i<s.size()-1; i++)
{
ans+=(p[i]+1)/2;
}
fout<<ans;
return 0;
}