Pagini recente » Cod sursa (job #1449866) | Cod sursa (job #2481863) | Cod sursa (job #2959048) | Cod sursa (job #1215013) | Cod sursa (job #2262542)
#define DM 2000005
#include <fstream>
using namespace std;
ifstream fi ("pscpld.in");
ofstream fo ("pscpld.out");
bool p;
char s[DM];
int dp[DM], n, m, d, crt;
long long rez;
string st;
bool ok(int a, int b) {
return a + b <= n && a - b >= 0;
}
int main() {
fi >> st;
for (int i = 0; i < st.size(); ++i) {
s[2*i] = '*';
s[2*i+1] = st[i];
}
n = 2*st.size();
s[2*st.size()] = '*';
m = d = crt = 1;
p = 0;
while (crt < n) {
if (crt > d)
p = 0;
dp[crt] = (p) ? min(dp[2*m-crt], d - crt):0;
int &a = dp[crt];
while (ok(crt, a) && s[crt+a] == s[crt-a]) {
++a;
}
--a;
if (d < crt + a) {
d = crt + a;
m = crt;
p = 1;
}
++crt;
}
for (int i = 0; i <= n; ++i)
rez += 1LL*(dp[i] + 1)/2;
fo << rez;
return 0;
}