Pagini recente » Cod sursa (job #1211131) | Cod sursa (job #866842) | Cod sursa (job #70547) | Cod sursa (job #869435) | Cod sursa (job #2452104)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
const int dim = 2000005;
int len[dim],n,aux;
long long int ans = 0;
char s[dim],v[dim];
void Algoritm()
{
int c = 0,r = 0;
for (int i=1; i<2*n+1; i++)
{
if (i < r)
{
len[i] = min(r-i , len[2*c-i]);
}
while (v[i-len[i]-1] == v[i+len[i]+1])
{
len[i]++;
}
ans += (long long int)((len[i] + 1)/2);
if (i + len[i] > r)
{
r = i+len[i];
c = i;
}
}
}
int main()
{
in >> (s+1);
n = strlen(s+1);
v[0] = '$';
for(int i=1; i<=n; i++)
{
v[++aux] = '$';
v[++aux] = s[i];
}
v[++aux] = '$';
Algoritm();
out << ans-1;
return 0;
}