Pagini recente » Borderou de evaluare (job #2014713) | Borderou de evaluare (job #978573) | Cod sursa (job #3361741) | Cod sursa (job #3363630) | Cod sursa (job #3363877)
#include <bits/stdc++.h>
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
char s[2000009];
char copie[1000009];
int n;
int l[2000009];
void manacher ()
{
s[1]='*';
for (int i=1; i<=n; i++)
s[2*i]=copie[i], s[2*i+1]='*';
int poz=0;
//cout << (s+1);
n=2*n+1;
for (int i=1; i<=n; i++)
{
if (poz+l[poz]<i)
{
poz=i;
int st=i-1, dr=i+1;
while (st>=1 && dr<=n && s[st]==s[dr])
{
st--;
dr++;
l[poz]++;
}
}
else
{
int ogl=2*poz-i;
if (poz+l[poz]>i+l[ogl])
l[i]=l[ogl];
else if (poz+l[poz]<i+l[ogl])
l[i]=poz+l[poz]-i;
else if (poz+l[poz]==i+l[ogl])
{
l[i]=l[ogl];
int st=i-l[i]-1, dr=i+l[i]+1;
bool ok=0;
while (st>=1 && dr<=n && s[st]==s[dr])
{
ok=1;
l[i]++;
st--;
dr++;
}
if (ok) poz=i;
}
}
}
}
signed main ()
{
f.getline (copie+1, 1000001);
n=strlen (copie+1);
manacher ();
int ans=0;
for (int i=1; i<=n; i++)
{
if (s[i]=='*')
{
ans+=l[i]/2;
//cout << l[i]/2<<'\n';
}
else
{
ans+=l[i]/2+1;
//cout << l[i]/2+1 <<'\n';
}
}
g << ans;
}