Pagini recente » Cod sursa (job #2546827) | Cod sursa (job #145157) | Cod sursa (job #703515) | Cod sursa (job #1954571) | Cod sursa (job #1414759)
#include <fstream>
#include <cstring>
using namespace std;
const int MAX_N = 1000002;
int N;
int D[2 * MAX_N];
long long ans;
char s[2 * MAX_N], t[MAX_N];
int main() {
ifstream f("pscpld.in");
ofstream g("pscpld.out");
t[0] = s[0] = ' ';
f >> (t + 1);
N = strlen(t) - 1;
s[1] = '#';
for(int i = 1; i <= N; ++i) {
s[2 * i] = t[i];
s[2 * i + 1] = '#';
}
N = 2 * N + 1;
for(int i = 1, C = 0, L = 0, R = 0; i <= N; ++i) {
if(i <= R) {
int j = 2 * C - i;
if(j - D[j] > L) {
D[i] = D[j];
}
else {
D[i] = j - L;
while(i - D[i] - 1 >= 1 && i + D[i] + 1 <= N && s[i - D[i] - 1] == s[i + D[i] + 1]) {
++D[i];
}
}
}
else {
D[i] = 0;
while(i - D[i] - 1 >= 1 && i + D[i] + 1 <= N && s[i - D[i] - 1] == s[i + D[i] + 1]) {
++D[i];
}
}
if(i + D[i] > R) {
C = i;
R = i + D[i];
L = i - D[i];
}
}
for(int i = 1; i <= N; ++i) {
if(s[i] == '#') {
ans += D[i] / 2;
}
else {
ans += D[i] / 2 + 1;
}
}
g << ans << "\n";
f.close();
g.close();
return 0;
}