Pagini recente » Cod sursa (job #936907) | Cod sursa (job #3238175) | Cod sursa (job #2702824) | Cod sursa (job #497588) | Cod sursa (job #843258)
Cod sursa(job #843258)
#include <fstream>
#include <string>
#include <iostream>
const int MAX_N = 1001000;
std::ifstream fin;
std::ofstream fout;
char s[2*MAX_N];
int l[2*MAX_N];
int N;
long long result;
inline int min(int a, int b) {
return a > b ? b : a;
}
inline int max(int a, int b) {
return a > b ? a : b;
}
int main(int argc, char const *argv[]) {
fin.open("pscpld.in");
char ch;
s[++N] = '@';
while (1) {
fin.get(ch);
if (ch == '\n')
break;
s[++N] = ch;
s[++N] = '@';
}
fin.close();
int best = 0;
for (int i = 1; i <= N; ++i) {
if (best + l[best] >= i) {
l[i] = min(best + l[best] - i, l[2 * best - i]);
}
while (i - l[i] - 1 >= 0 && i + l[i] + 1 <= N &&
s[i - l[i] - 1] == s[i + l[i] + 1]) {
++l[i];
}
if (i + l[i] > best + l[best]) {
best = i;
}
}
result = 0;
for (int i = 1; i <= N; ++i) {
if (i % 2 == 0)
result += (l[i] + 1) / 2;
else
result += l[i] / 2;
}
fout.open("pscpld.out");
fout << result;
fout.close();
return 0;
}