Pagini recente » Cod sursa (job #2846004) | Cod sursa (job #1076270) | Cod sursa (job #1829825) | Cod sursa (job #2331078) | Cod sursa (job #2763052)
#include <iostream>
#include <fstream>
#include <cstring>
#include <istream>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
char s[2000005];
int v[2000005];
int main()
{
int n,i,mijpalc=0,lpalc=0,j,maxim=-1,sume=0;
fin.getline(s,2000005);
n=strlen(s);
for(i=n-1;i>0;i--)
{
s[i*2+1]=s[i];
s[i*2]='*';
}
s[0]='#';
s[2*n]='$';
for(j=1;j<2*n;j++)
{
if(j>mijpalc+lpalc)
{
mijpalc=j;
for(lpalc=1;lpalc<=n && lpalc<=j;lpalc++)
if(s[lpalc+mijpalc]!=s[mijpalc-lpalc])
break;
lpalc--,v[j]=lpalc;
}
else
{
/// capat stanga palogl > capat stanga palindrom mare
/// 2*mij-j-v[2*mij-j]> mijpalc-lpalc
if(2*mijpalc-j-v[2*mijpalc-j]>mijpalc-lpalc)
v[j]=v[2*mijpalc-j];
else
{
lpalc=mijpalc+lpalc-j;
mijpalc=j;
while(s[mijpalc+lpalc+1]==s[mijpalc-lpalc-1])
{
lpalc++;
}
v[j]=lpalc;
}
}
}
for(i=1;i<2*n;i++)
if(i%2==0)
{
v[i]=(v[i]+1)/2;
}
else
{
v[i]=v[i]/2;
v[i]=v[i]+1;
}
for(i=1;i<2*n;i++)
sume+=v[i];
fout<<sume;
return 0;
}