Pagini recente » Cod sursa (job #451943) | Cod sursa (job #12898) | Cod sursa (job #238967) | Cod sursa (job #961867) | Cod sursa (job #2926525)
#include <bits/stdc++.h>
using namespace std;
ifstream in ("scpld.in");
ofstream out ("scpld.out");
string pp (string s)
{
string q = "^";
for (int i=0; i<s.size(); i++)
{
q += '#';
q += s[i];
}
q += "#$";
return q;
}
int n;
int l[2000001];
long long manacher(string s)
{
string q = pp(s);
n = q.size();
int c=0, r=0;
for (int i=1; i+1<n; i++)
{
int mirr = c+c-i;
l[i] = (r > i) ? min(l[mirr], r-i) : 0;
while (q[i+1 + l[i]] == q[i-1 - l[i]])
l[i]++;
if (i + l[i] > r)
{
c = i;
r = i + l[i];
}
}
long long ans = 0;
/**
l = 2*k-1 => 2*1-1, 2*2-1, ..., 2*k-1 => k
l = 2*k => 2*1, 2*2, ..., 2*k => k
*/
for (int i=1; i+1<n; i++)
l[i] = (l[i] + 1) / 2, ans += l[i];
return ans;
}
int main()
{
string s;
in >> s;
out << manacher(s);
return 0;
}