Pagini recente » Cod sursa (job #1217693) | Cod sursa (job #927078) | Cod sursa (job #1126181) | Cod sursa (job #2871943) | Cod sursa (job #2737055)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
int len;
int64_t lps[2000100];
string x;
int64_t manacher()
{
int c = 0, r = 0;
for(int i = 1; i < len - 1; i++)
{
int mirror = 2 * c - i;
if(i < r)
lps[i] = min(lps[mirror], (int64_t)r - i);
int64_t a = i + lps[i] + 1;
int64_t b = i - lps[i] - 1;
while(a < len && b >= 0 && x[a] == x[b])
{
lps[i]++;
a++;
b--;
}
if(i + lps[i] > r)
{
r = i + lps[i];
c = i;
}
}
int64_t ans = 0;
for(int i = 1; i < len - 1; i++)
{
//cout << i << ' ' << x[i] << ' ' << lps[i] << '\n';
if(x[i] == '#')
ans += lps[i] / 2;
else
ans += lps[i] / 2 + 1;
}
return ans;
}
int main()
{
string aux;
in >> aux;
int k = aux.size();
x[len++] = '#';
for(int i = 0; i < k; i++)
{
x[len++] = aux[i];
x[len++] = '#';
}
out << manacher() << '\n';
return 0;
}