Pagini recente » Cod sursa (job #2065375) | Cod sursa (job #2109699) | Cod sursa (job #2445332) | Cod sursa (job #788673) | Cod sursa (job #1252672)
//babcbAbCbaccba
#include <fstream>
#include <cstring>
#define DIMN 2000005
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
int n, len;
char s[DIMN], S[DIMN];
int P[DIMN];
inline int minim(int x, int y) {
return (x < y ? x : y);
}
int main() {
f.get(s, DIMN);
len = strlen(s);
for (int i = 1; i <= len; ++i) {
S[2 * i - 1] = '#';
S[2 * i] = s[i - 1];
}
n = len * 2 + 1;
S[n] = '#';
S[n + 1] = '\0';
int C = 0, R = 0;
for (int i = 2; i < n; ++i) {
int i_mirror = 2 * C - i;
P[i] = R>i ? minim(R - i, P[i_mirror]) : 0;
while (i - P[i] - 1 > 0 && S[i - P[i] - 1] == S[i + P[i] + 1])
++P[i];
if (i + P[i] > R) {
C = i;
R = i + P[i];
}
}
long long SOL = 0;
for (int i = 1; i <= n; ++i)
if (S[i] == '#')
SOL += P[i] / 2;
else
SOL += 1 + P[i] / 2;
g << SOL;
return 0;
}
//Trust me, I'm the Doctor!