Pagini recente » Cod sursa (job #1477301) | Cod sursa (job #3262043) | Cod sursa (job #3164883) | Cod sursa (job #2630071) | Cod sursa (job #1266403)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
long long manacher(char *s) {
int len = strlen(s);
vector<char> S(len+len+10);
vector<int> P(len+len+10);
for (int i = 1; i <= len; ++i) {
S[2 * i - 1] = '#';
S[2 * i] = s[i - 1];
}
int 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 ? min(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 sum = 0;
for (int i = 1; i <= n; ++i)
if (S[i] == '#')
sum += P[i] / 2;
else
sum += 1 + P[i] / 2;
return sum;
}
#define maxdim 1000005
int main() {
char s[maxdim];
f >> s;
g << manacher(s);
return 0;
}