Pagini recente » Cod sursa (job #1553236) | Cod sursa (job #840642) | Cod sursa (job #1634410) | Cod sursa (job #2303242) | Cod sursa (job #2806242)
#include <fstream>
#define N 1000004
#include <cstring>
using namespace std;
char ch[2 * N], s[N];
int lp[2 * N];
int main()
{
ifstream f("pscpld.in");
ofstream g("pscpld.out");
int n, c, lg, exp, dr, i, ii;
f >> ch;
n = strlen(ch);
lg = -1;
for (i = 0;i < n;++i)
{
s[++lg] = '!';
s[++lg] = ch[i];
}
s[++lg] = '!';
long long ss = n;
c = 1, dr = 2;
lp[1] = 1;
for (i = 2;i <= lg;++i)
{
ii = c - (i - c);
exp = 0;
if (dr <= i)
exp = 1;
else
{
if (lp[ii] < dr - i)///se gaseste in palindromul mare, dar nu e prefix
lp[i] = lp[ii];
else
if (lp[ii] == dr - i)///e prefix al palindromului mare
lp[i] = lp[ii], exp = 1;
else
if (lp[ii] > dr - i)///se afla in exteriorul palindromului
lp[i] = dr - i, exp = 1;
}
if (exp)
{
while (i - lp[i] - 1 >= 0 && i + lp[i] + 1 <= lg)
if ((i - lp[i]) % 2 != 0)
++lp[i];
else
if (s[i - lp[i] - 1] == s[i + lp[i] + 1])
++lp[i];
else
break;
}
if (dr < i + lp[i])
dr = i + lp[i], c = i;
ss = ss + (long long)lp[i] / 2;
}
g << ss << '\n';
f.close();
g.close();
return 0;
}