Pagini recente » Cod sursa (job #2548387) | Cod sursa (job #1359027) | Cod sursa (job #1486493) | Cod sursa (job #2398485) | Cod sursa (job #3247201)
#include <bits/stdc++.h>
const std :: string FILENAME = "pscpld";
std :: ifstream f (FILENAME + ".in");
std :: ofstream g (FILENAME + ".out");
const long long NMAX = 2e6 + 5;
long long ans;
long long p[NMAX];
std :: string s;
inline std :: string modif(const std :: string & s)
{
std :: string aux = "@";
for(auto & i : s)
{
aux += "#";
aux += i;
}
aux += "#*";
return aux;
}
inline void manacher(const std :: string & s)
{
long long r = 0;
long long c = 0;
for(long long i = 1; i < s.size() - 1; i ++)
{
long long sim = 2 * c - i;
if(i < r)
{
p[i] = std :: min(r - i, p[sim]);
}
while(s[i - p[i] - 1] == s[i + p[i] + 1])
{
p[i] ++;
}
if(r < i + p[i])
{
r = p[i];
c = i;
}
}
}
int main()
{
f >> s;
s = modif(s);
manacher(s);
for(long long i = 1; i < s.size() - 1; i ++)
{
ans += ceil(1.00 * p[i] / 2);
}
g << ans;
return 0;
}