Pagini recente » Cod sursa (job #1393132) | Cod sursa (job #3182351) | Cod sursa (job #995582) | Cod sursa (job #2988590) | Cod sursa (job #468138)
Cod sursa(job #468138)
#include <iostream>
using namespace std;
#define maxn 1000010
int N, L[maxn];
long long sol;
char D[maxn];
void palindromimpar() {
int i, mxx;
L[1] = 0; mxx = 1;
for(i=2; i<=N; i++) {
if(i < mxx + L[mxx]) {
L[i] = min(L[mxx - (i - mxx)], mxx + L[mxx] - i);
}
if(mxx + L[mxx] <= i + L[i]) {
mxx = i;
while(1 <= i - L[i] - 1 && i + L[i] + 1 <= N && D[i + L[i] + 1] == D[i - L[i] - 1]) {
L[i]++;
}
}
}
}
void palindrompar() {
int i, mxx;
if(D[1] == D[2]) {
L[1] = 1; mxx = 1;
}
else {
L[1] = 0; mxx = 1;
}
for(i=2; i<=N; i++) {
if(i < mxx + L[mxx]) {
L[i] = min(L[mxx - (i - mxx)], mxx + L[mxx] - i);
}
if(mxx + L[mxx] <= i + L[i]) {
mxx = i;
while(1 <= i - (L[i] + 1) + 1 && i + L[i] + 1 <= N && D[i + L[i] + 1] == D[i - (L[i] + 1) + 1]) {
L[i]++;
}
}
}
}
int main() {
FILE *f1=fopen("pscpld.in", "r"), *f2=fopen("pscpld.out", "w");
int i, j, p, q;
fscanf(f1, "%s", D+1);
N = strlen(D+1);
palindromimpar();
for(i=1; i<=N; i++) {
sol += (L[i] + 1);
}
memset(L, 0, sizeof(L));
palindrompar();
for(i=1; i<=N; i++) {
sol += L[i];
}
fprintf(f2, "%lld\n", sol);
fclose(f1); fclose(f2);
return 0;
}