Pagini recente » Statistici Guzu Daniel-Emanuel (guzudaniel) | Cod sursa (job #970914) | Cod sursa (job #305064) | Cod sursa (job #104448) | Cod sursa (job #2008957)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
const int maxn = 2000005;
char aux[maxn * 2];
char T[maxn];
int p[maxn];
int rez;
int main()
{
in.getline(aux + 1, maxn);
int n1 = strlen(aux + 1);
int n = 0;
for(int i = 1; i <= n1; i++)
{
T[++n] = aux[i];
T[++n] = '#';
}
T[0] = '?';
T[n] = '!';
n--;
int st = 0;
int dr = 0;
for(int i = 1; i <= n; i++)
{
if(i <= dr)
p[i] = min(p[st + dr - i], dr - i + 1);
else
p[i] = 1;
while(T[i - p[i]] == T[i + p[i]])
p[i]++;
if(i + p[i] - 1 > dr)
{
st = i - p[i] + 1;
dr = i + p[i] - 1;
}
}
long long s = 0;
for(int i = 1; i <= n; i++)
{
if(isalpha(T[i]))
s = s + (p[i] + 1) / 2;
else
s = s + p[i] / 2;
}
//for(int i = 1; i <= n; i++)
//cerr << p[i] << " ";
out << s << "\n";
return 0;
}