Pagini recente » Cod sursa (job #2267600) | Cod sursa (job #2666571) | Cod sursa (job #1411316) | Cod sursa (job #2921770) | Cod sursa (job #2699184)
#include <fstream>
#include <string>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
int Pal[2000005], v[2000005];
void Manacher(string s)
{
v[0] = -2;
v[2 * s.size() + 2] = -3;
for(int i = 1; i <= 2 * s.size() + 1; i += 2)
v[i] = -1;
for(int i = 0; i < s.size(); i++)
v[2 * i + 2] = (s[i] - 'a');
int C, R;
C = R = 0;
for(int i = 1; i <= 2 * s.size() + 1; i++)
{
int mirror = 2 * C - i;
if(i < R)
Pal[i] = min(R - i, Pal[mirror]);
while(v[i + Pal[i] + 1] == v[i - Pal[i] - 1])
Pal[i]++;
if(i + Pal[i] > R)
{
C = i;
R = i + Pal[i];
}
}
long long ans = 0;
for(int i = 1; i <= 2 * s.size() + 1; i++)
ans += (long long)(Pal[i] / 2);
fout << ans + (long long)s.size() << '\n';
}
int main()
{
string s;
fin >> s;
Manacher(s);
return 0;
}