Pagini recente » Cod sursa (job #3178140) | Cod sursa (job #1455596) | Cod sursa (job #2877466) | Cod sursa (job #2177667) | Cod sursa (job #2701401)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
char buff[1000001], c[2000005];
int pal[2000005];
int main()
{
int nbuff, n, i, st, dr, k;
fin >> buff;
nbuff = strlen(buff);
c[0] = '#';
for (i = 0; i<nbuff; i++)
{
c[2*i+1] = buff[i];
c[2*i+2] = '#';
}
n = nbuff*2 + 3;
st = dr = -1;
for (i = 0; i<n; i++)
{
if (i <= dr)
k = min(pal[st + dr - i], dr - i + 1);
else
k = 1;
while (0 <= i-k && i+k < n && c[i-k] == c[i+k])
k++;
pal[i] = k;
k--;
if (i + k > dr)
{
dr = i + k;
st = i - k;
}
}
long long rasp = 0;
for (i = 0; i<n; i++)
rasp = rasp + pal[i]/2;
fout << rasp;
return 0;
}