Pagini recente » Cod sursa (job #2087583) | Cod sursa (job #3241628) | Cod sursa (job #1112851) | Cod sursa (job #1650875) | Cod sursa (job #1832566)
#include <string>
#include <fstream>
#include <cstring>
#define NMAX 2000000
using namespace std;
char c[NMAX + 1000];
char cit[NMAX / 2 + 1000];
int pal[NMAX + 1000]; /// cel mai lung pal cu centrul in x
int n, m, piv, l;
int main()
{
ifstream in("pscpld.in");
in >> cit;
m = strlen(cit);
for (int i(0); i < m; i++) {
c[2 * i] = cit[i];
c[2 * i + 1] = '$';
}
n = 2 * m - 1;
piv = -1, l = -1;
for (int i(0); i < n; i++) {
if (i > piv + l) {
piv = i;
l = 0;
while (i - l - 1 >= 0 && i + l + 1 < n && c[i - l - 1] == c[i + l + 1])
l++;
pal[i] = l;
}
else {
int p(pal[2 * piv - i]);
if (i + p > piv + l)
pal[i] = piv + l - i;
else if (i + p < piv + l)
pal[i] = p;
else {
piv = i, l = p;
while (i - l - 1 >= 0 && i + l + 1 < n && c[i - l - 1] == c[i + l + 1])
l++;
pal[i] = l;
}
}
}
long long rez(0);
for (int i(0); i < n; i++) {
if (c[i] == '$')
rez += 1ll * (pal[i] + 1) / 2;
else
rez += 1ll + 1ll * pal[i] / 2;
}
ofstream out("pscpld.out");
out << rez;
return 0;
}