Pagini recente » Cod sursa (job #2465975) | Cod sursa (job #716802) | Cod sursa (job #2108638) | Cod sursa (job #2849893) | Cod sursa (job #1345708)
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
using namespace std;
const int NMAX = 1000000;
int p[NMAX * 2 + 1];
string v;
char s[NMAX + 5];
void solve(int poz, int n) {
while(poz - p[poz] >= 0 && poz + p[poz] < n && v[poz - p[poz]] == v[poz + p[poz]])
++ p[poz];
-- p[poz];
}
int main() {
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
int n, j = 0, aux, st, dr;
long long rasp = 0;
gets(s);
n = strlen(s);
for(int i = 0; i < n; ++ i) {
v = v + "#" + s[i];
}
v += "#";
n = n * 2 + 1;
for(int i = 0; i < n; ++ i) {
aux = 2 * j - i;
st = j - p[j];
dr = j + p[j];
if( i > dr ) {
solve(i, n);
j = i;
} else
if( aux - p[aux] > st ) {
p[i] = p[aux];
} else {
p[i] = dr - i;
solve(i, n);
j = i;
}
}
for(int i = 0; i < n; ++ i) {
rasp += (p[i] + 1) / 2;
//printf("%d ", p[i]);
}
printf("%lld", rasp);
return 0;
}