Pagini recente » Monitorul de evaluare | Borderou de evaluare (job #3327413) | Cod sursa (job #3336752) | Borderou de evaluare (job #3325774) | Cod sursa (job #3304101)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
#define int long long
int manacher(const string &t)
{
string s = "";
for(char ch : t)
{
s += ch;
s += '*';
}
//cout<<s;
//cout<<'\n';
vector<int> aux(s.size(), 0);
int centru = 0, dr = 1, ans = 0;
for(int i = 0; i < s.size(); i++)
{
int st = 2 * centru - i;
if(i < dr)
aux[i] = min(dr - i, aux[st]);
while(i + aux[i] < s.size() && i - aux[i] >= 0 && s[i + aux[i]] == s[i - aux[i]])
aux[i]++;
if(i + aux[i] > dr)
{
dr = i + aux[i];
centru = i;
}
ans += aux[i]/2+(s[i+aux[i]-1]!='*'&&s[i]!='*');
//cout<<i<<' '<<aux[i]<<' '<<ans<<'\n';
}
return ans;
}
signed main()
{
string s;
fin >> s;
fout << manacher(s);
fin.close();
fout.close();
return 0;
}