Pagini recente » Cod sursa (job #3320376) | Cod sursa (job #3344911) | Cod sursa (job #3353724) | Cod sursa (job #3342824) | Cod sursa (job #3304100)
#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] + 1 < s.size() && i - aux[i] - 1 >= 0 && s[i + aux[i] + 1] == s[i - aux[i] - 1])
aux[i]++;
if(i + aux[i] > dr)
{
dr = i + aux[i];
centru = i;
}
ans += (s[i] == '*' ? (aux[i] / 2) : (aux[i] / 2 + 1));
}
return ans;
}
signed main()
{
string s;
fin >> s;
fout << manacher(s);
fin.close();
fout.close();
return 0;
}