Pagini recente » Cod sursa (job #2535360) | Cod sursa (job #1418719) | Cod sursa (job #2728860) | Cod sursa (job #1676938) | Cod sursa (job #2798631)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
string temp, s;
int v[2000005];
long long ans;
int main()
{
fin >> temp;
int len = temp.size();
s = '$';
for(int i = 1; i <= len; i++)
{
s += temp [i - 1];
s += '$';
}
len *= 2;
int poz = 0, dr = 0;
for(int i = 1; i < len; i++)
{
int sim = 2 * poz - i;
if(dr > i)
v[i] = min(dr - i, v[sim]);
while(i >= v[i] + 1 && s[i + v[i] + 1] == s[i - 1 - v[i]])
v[i]++;
if(i + v[i] > dr)
{
poz = i;
dr = i + v[i];
}
if(i % 2 == 1)
ans += (v[i] + 1) / 2;
else
ans += v[i] / 2;
}
fout << ans;
return 0;
}