Pagini recente » Cod sursa (job #1692319) | Cod sursa (job #794567) | Istoria paginii runda/mereuafectatemotional/clasament | Cod sursa (job #358767) | Cod sursa (job #1393963)
#include <fstream>
#include <cstring>
#define NMAX 1000005
using namespace std;
int n,sol,i2,st,dr;
int p[NMAX*2];
char s[NMAX],v[NMAX*2];
void extinde(int poz)
{
while(poz - p[poz] > 0 && poz + p[poz] <= n && v[poz - p[poz]] == v[poz + p[poz]]) ++p[poz];
--p[poz];
}
int main()
{
ifstream f("pscpld.in");
ofstream g("pscpld.out");
f.getline(s+1,NMAX);
n = strlen(s+1);
for(int i = n; i >= 0; --i)
{
v[2*i]=s[i];
v[2*i+1]='#';
}
int c = 1;
n = n * 2 +1;
for(int i = 2; i <= n; ++i)
{
i2 = 2 * c - i;
st = c - p[c];
dr = c + p[c];
if (i > dr)
{
extinde(i);
c = i;
}
else
{
if (i2 - p[i2] > st)
{
p[i] = p[i2];
}
else
{
p[i] = dr - i;
extinde(i);
c = i;
}
}
}
for(int i = 1; i <= n; ++i)
sol += (p[i]/2);
sol += (n/2);
g<<sol<<"\n";
}