Pagini recente » Cod sursa (job #658497) | Cod sursa (job #63807) | Cod sursa (job #538811) | Cod sursa (job #829229) | Cod sursa (job #2262533)
#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, rez;
string st;
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 &aux = dp[crt];
while (s[crt+aux] == s[crt-aux]) {
++aux;
}
--aux;
if (d < crt + aux) {
d = crt + aux;
m = crt;
p = 1;
}
++crt;
}
for (int i = 0; i <= n; ++i)
rez += (dp[i] + 1)/2;
fo << rez;
return 0;
}