Pagini recente » Cod sursa (job #2122568) | Cod sursa (job #1938294) | Cod sursa (job #2255637) | Cod sursa (job #837063) | Cod sursa (job #2886960)
#include <fstream>
#include <string>
using namespace std;
ifstream fin ("pscpld.in");
ofstream fout ("pscpld.out");
string a, buff;
int pal[2000001];
int main()
{
int n, i, l, st, dr;
fin >> buff;
a += '#';
for (i = 0; i<buff.size(); i++)
{
a += buff[i];
a += '#';
}
n = a.size();
st = dr = -1;
for (i = 0; i<n; i++)
{
if (i <= dr)
l = min (dr-i+1, pal[st+dr-i]);
else
l = 1;
while (0 <= i-l && i+l < n && a[i-l] == a[i+l])
l++;
pal[i] = l;
if (i+l-1 > dr)
{
st = i-l+1;
dr = i+l-1;
}
}
long long rasp = 0;
for (i = 0; i<n; i++)
rasp = rasp + pal[i]/2;
fout << rasp;
return 0;
}