Pagini recente » Cod sursa (job #605138) | Cod sursa (job #1451767) | Cod sursa (job #739960) | Cod sursa (job #2737906) | Cod sursa (job #1671942)
# include <bits/stdc++.h>
# define NR 2000005
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
int i,j,n,m,CI,CS,VV,mid;
int P[NR], v[NR];
char s[NR];
long long sol;
int main ()
{
f.getline(s+1, NR); n=strlen(s+1);
for (i=1; i<=n; ++i) {
v[++VV]='$';
v[++VV]=s[i];
}
v[++VV]='$';
// P[i] - lungimea palindromului de lungime impara in i
for (i=1; i<=VV; ++i) {
if (CS<i) { // nu e in niciun palindrom
CI=CS=i; P[i]=1; mid=i;
while (1<CI && CS<VV && v[CI-1]==v[CS+1]) {
P[i]+=2;
--CI; ++CS;
}
} else { // este cuprins intr-un palindrom
int poz=mid - (i-mid);
if (poz - P[poz] + 1==CI) { // pot extinde
P[i]=P[poz]; mid=i;
CI=i-(CS-i);
while (1<CI && CS<VV && v[CI-1]==v[CS+1]) {
P[i]+=2;
--CI; ++CS;
}
} else {
if (P[poz]>CI) P[i]=P[poz];
else P[i]=CS-i;
}
}
}
for (i=1; i<=VV; ++i)
sol=sol + P[i]/2;
g<<sol<<"\n";
return 0;
}