Pagini recente » Cod sursa (job #3319449) | Cod sursa (job #3337475) | Cod sursa (job #3304338) | Cod sursa (job #3327052) | Cod sursa (job #3304102)
#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 += '*';
}
vector<int> aux(s.size(), 0);
int centru = 0, dr = 0, 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] != '*');
}
return ans;
}
signed main()
{
string s;
fin >> s;
fout << manacher(s);
fin.close();
fout.close();
return 0;
}