Pagini recente » Cod sursa (job #3211861) | Cod sursa (job #2935076) | Cod sursa (job #2621148) | Cod sursa (job #2019608) | Cod sursa (job #3237149)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin ("pscpld.in");
ofstream fout ("pscpld.out");
int n,i,l,poz,pozpal,lg[1000005];
char sir[1000005],sirc[1000005];
long long sol;
int main ()
{
///dbdedbd => dbd din dreapta = dbd din stanga => b din dreapta minim palindrom lg[stanga]
fin>>sirc;
strcpy (sir+1,sirc);
n=strlen (sir+1);
poz=0;
for (i=1; i<=n; i++)
{
if (i<=poz)
lg[i]=min (lg[pozpal-l+1+poz-i],poz-i+1);
while (i-lg[i]>0&&i+lg[i]<=n&&sir[i-lg[i]]==sir[i+lg[i]])
lg[i]++;
if (i+lg[i]-1>poz)
{
l=lg[i];
poz=i+lg[i]-1;
pozpal=i;
}
sol+=lg[i];
}
poz=0;
for (i=1; i<n; i++)
{
lg[i]=0;
if (i+1<=poz)
lg[i]=min (lg[pozpal-l+1+poz-i],poz-i+1);
while (i-lg[i]>0&&i+1+lg[i]<=n&&sir[i-lg[i]]==sir[i+1+lg[i]])
lg[i]++;
if (i+lg[i]>poz)
{
l=lg[i];
poz=i+lg[i];
pozpal=i;
}
sol+=lg[i];
}
fout<<sol;
return 0;
}