Pagini recente » Cod sursa (job #2307986) | Cod sursa (job #1110862) | Cod sursa (job #2664349) | Cod sursa (job #497185) | Cod sursa (job #2739071)
#include <fstream>
#include <string>
using namespace std;
ifstream fin ("pscpld.in");
ofstream fout ("pscpld.out");
string buff, a;
int pal[2000005];
int main()
{
int n, i, l, st, dr;
long long rasp = 0;
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(pal[st + dr - i], dr - i + 1);
else
l = 1;
while (0 <= i-l && i + l < n && a[i-l] == a[i+l])
l++;
pal[i] = l;
l--;
if (i + l > dr)
{
dr = i + l;
st = i - l;
}
}
for (i = 0; i<n; i++)
rasp = rasp + pal[i]/2;
fout << rasp;
return 0;
}