Pagini recente » Cod sursa (job #2688373) | Cod sursa (job #802862) | Cod sursa (job #1821275) | Cod sursa (job #3278067) | Cod sursa (job #2582060)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
vector <int> manacher(string s, bool par)
{
vector <int> best(s.size(), 0);
int n = s.size();
int l = 0;
int r = 0;
for(int i = 0; i < n - !par; ++i)
{
if(i + !par < r)
best[i] = min(r - i, best[l + r - i - !par]);
int posl = i - best[i] + !par;
int posr = i + best[i];
while(posl - 1 >= 0 && posr + 1 < n && s[posl - 1] == s[posr + 1])
{
--posl;
++posr;
++best[i];
}
if(posr > r)
{
r = posr;
l = posl;
}
}
return best;
}
main()
{
string s;
fin >> s;
vector <int> par = manacher(s, 0);
vector <int> impar = manacher(s, 1);
long long cnt = 0;
for(auto i : par)
cnt += i;
for(auto i : impar)
cnt += i + 1;
fout << cnt << '\n';
}