Pagini recente » Cod sursa (job #1941170) | Cod sursa (job #906556) | Cod sursa (job #3120625) | Cod sursa (job #1617527) | Cod sursa (job #2886961)
#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.push_back ('#');
for (i = 0; i<buff.size(); i++)
{
a.push_back (buff[i]);
a.push_back ('#');
}
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;
}