Pagini recente » Cod sursa (job #714703) | Diferente pentru implica-te/arhiva-educationala intre reviziile 223 si 174 | Cod sursa (job #3131283) | Cod sursa (job #3220282) | Cod sursa (job #3294657)
#include <stdio.h>
#include <ctype.h>
using namespace std;
#define MAXN 1000000
char v[2 * MAXN + 1];
int p[2 * MAXN + 1];
int minim(int a, int b) {
return a < b ? a : b;
}
int main()
{
//manacher
int n, i, dr, mij, st;
long long rez;
char ch;
n = 1;
v[0] = '#';
ch = fgetc(stdin);
while (isalpha(ch)) {
v[n] = ch;
v[n + 1] = '#';
n += 2;
ch = fgetc(stdin);
}
dr = mij = -1;
rez = 0;
for (i = 0; i < n; i++) {
st = 2 * mij - i;
if (st >= 0) {
p[i] = minim(dr - i, p[st]);
}
while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n && v[i - p[i] - 1] == v[i + p[i] + 1]) {
p[i]++;
}
if (i % 2 > 0) {
rez += p[i] / 2 + 1;//daca e litera
} else {
rez += p[i] / 2;//daca e #
}
if (i + p[i] > dr) {
dr = i + p[i];
mij = i;
}
}
printf("%lld\n", rez);
return 0;
}