Pagini recente » Cod sursa (job #1864184) | Cod sursa (job #3132661) | Cod sursa (job #2264970) | Cod sursa (job #3219717) | Cod sursa (job #2654345)
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
char v[1000000];
int d1[1000000],d2[1000000],n;
int trivial(int k, int i)
{
while(v[i-k]==v[i+k]&&i-k>=0&&i+k<n)
k++;
return k;
}
int mn(int a, int b)
{
return a>b?b:a;
}
int main()
{
f>>v;
n=strlen(v);
int l1=0,l2=0,r2=-1,r1=-1,s=0;
for(int i=0;i<n;i++)
{
int k=(i>r1)?1:mn(d1[l1+r1-i],d1[l1+r1-i]-r1+i);
d1[i]=trivial(k,i);
s+=d1[i];
if(i+d1[i]>r1) {l1=i-d1[i]+1; r1=i+d1[i]-1;}
k=(i>r2)?0:mn(d2[l2+r2-i+1],r2+i-1);
while (0 <= i - k - 1 && i + k < n && v[i - k - 1] == v[i + k]) {
k++;
}
d2[i] = k--;
if (i + k > r2) {
l2 = i - k - 1;
r2 = i + k ;
}
s+=d2[i];
}
g<<s;
return 0;
}