Pagini recente » Cod sursa (job #589959) | Cod sursa (job #529589) | Cod sursa (job #1074295) | Cod sursa (job #2172665) | Cod sursa (job #2768475)
#include <fstream>
using namespace std;
int p[2000005];
string s, aux;
void read() {
int i;
ifstream f("pscpld.in");
s = '#';
f >> aux;
for (i = 0; i < aux.size(); i++) {
s += aux[i];
s += '#';
}
f.close();
}
long long nr;
void solve() {
int i, C, R, i_mirror;
C = 0, R = 0;
for (i = 1; i < s.size(); i++) {
i_mirror = C - (i - C);
if (R > i)
p[i] = min(R - i, p[i_mirror]);
else p[i] = 0;
while (i + 1 + p[i] < s.size() && i - 1 - p[i] >= 0 && s[i + 1 + p[i]] == s[i - 1 - p[i]])
p[i]++;
if (i + p[i] > R) {
C = i;
R = i + p[i];
}
nr += (p[i] + 1) / 2;
}
}
void output() {
ofstream g("pscpld.out");
g << nr;
g.close();
}
int main() {
read();
solve();
output();
return 0;
}