Pagini recente » Istoria paginii runda/minune10/clasament | Cod sursa (job #1654718) | Cod sursa (job #1870837) | Cod sursa (job #2150518) | Cod sursa (job #1880288)
#include <iostream>
#include <cstdio>
#include <cstring>
#define NMAX 1000005
#define LMAX 4 * NMAX
using namespace std;
char tmp[NMAX];
char sirInit[NMAX];
int l=1, i1;
int lps[LMAX];
int st, dr, c;
int rez;
void print()
{
for(int i=1; i<strlen(sirInit); i++)
{
if(lps[i] % 2 == 0)
rez += lps[i] / 2;
else
rez += lps[i] / 2 +1;
}
printf("%d",rez);
}
void solve()
{
lps[0] = 0;
lps[1] = 1;
c = 1, dr=2, i1;
int s, d;
for (int i=2; i<strlen(sirInit); ++i)
{
i1 = 2 * c - i;
if (i < dr)
lps[i] = min(lps[i1], dr - i);
else if (i >= dr)
lps[i] = 0;
st = i-1, dr = i + 1;
while (sirInit[st] == sirInit[dr])
{
st--, dr++;
lps[i]++;
}
if (i + lps[i] > dr)
{
dr = i + lps[i];
c = i;
}
}
}
void prelucrare()
{
sirInit[0] = '#';
for (int i=0; i<strlen(tmp); ++i)
{
sirInit[l] = tmp[i];
sirInit[l+1] = '#';
l+=2;
}
}
int main()
{
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
gets(tmp);
prelucrare();
solve();
print();
return 0;
}