Pagini recente » Cod sursa (job #2170267) | Cod sursa (job #678777) | Cod sursa (job #2196272) | Cod sursa (job #2469776) | Cod sursa (job #2883298)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
using ll = long long;
const int NMAX(1000005);
int lg[2 * NMAX];
inline void manacher(){
string s;
fin >> s;
string ax1 = "$";
for(auto it: s)
ax1 += it, ax1 += "$";
ll rez = 0;
int dr = 0, cen = 0;
for(int i = 1; i < (int)ax1.size(); ++i){
if(i <= dr)
lg[i] = min(dr - i + 1, lg[2 * cen - i]);
while(i + lg[i] < (int)ax1.size() && i - lg[i] >= 0 && ax1[i - lg[i]] == ax1[i + lg[i]])
++lg[i];
if(i + lg[i] - 1 > dr){
dr = i + lg[i] - 1;
cen = i;
}
if(i % 2)
rez += ((lg[i] + 1) / 2);
else rez += (lg[i]) / 2;
}
fout << rez << '\n';
}
int main()
{
manacher();
return 0;
}