Pagini recente » Cod sursa (job #2686016) | Cod sursa (job #106377) | Cod sursa (job #1466807) | Cod sursa (job #1056606) | Cod sursa (job #2798458)
#include <bits/stdc++.h>
using namespace std;
ifstream r("pscpld.in");
ofstream w("pscpld.out");
int n;
int m[2000010];
string s, aux;
void manacher()
{
int r=0, mij=0;
for(int i=1;i<=n;i++)
{
if(i<r&&i+m[2*mij-i]<r)
{
m[i] = m[mij - (i - mij)];
continue;
}
int x = 0;
if(i<r){
x=r-i;
}
while(s[i+x+1]==s[i-x-1]){
x++;
}
if(i+x>r){
r=i+x;
mij=i;
}
m[i]=x;
}
}
int main()
{
r>>aux;
s="#";
for (int i=0;i<aux.size()-1;i++)
{
s+=aux[i];
s+="*";
}
s+=aux[aux.size()-1];
s+="$";
n=s.size()-2;
manacher();
long long ans=0;
for (int i=1;i<=n;i++)
{
if(i&1)
{
ans += (long long)(m[i] / 2 + 1);
}
else
{
ans += (long long)((m[i] + 1) / 2);
}
}
w<<ans;
return 0;
}