Pagini recente » Cod sursa (job #1353636) | Cod sursa (job #1434523) | Cod sursa (job #648641) | Cod sursa (job #494249) | Cod sursa (job #2941727)
#include <fstream>
#include <string>
const int NMAX = 2e6 + 5;
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
int N;
long long ans;
int manacher[NMAX];
string tmp, s;
inline string get_manacher_string(string tmp)
{
string s = "$";
for (auto c: tmp)
{
s += "#";
s += c;
}
s += "#^";
return s;
}
inline void get_manacher()
{
N = s.length();
int mid = 0, dr = 0, mirr;
for (int i = 1 ; i < N - 1 ; ++ i)
{
mirr = mid + mid - i;
if (i <= dr)
{
manacher[i] = min(manacher[mirr], dr - i);
}
while (s[i - manacher[i] - 1] == s[i + manacher[i] + 1])
manacher[i] ++;
if (i + manacher[i] > dr)
{
dr = i + manacher[i];
mid = i;
}
}
}
int main()
{
f >> tmp;
s = get_manacher_string(tmp);
get_manacher();
for (int i = 1 ; i < N - 1 ; ++ i)
{
ans += 1LL * (manacher[i] + 1) / 2;
}
g << ans;
}