Pagini recente » Cod sursa (job #1141862) | Cod sursa (job #1442140) | Cod sursa (job #2118629) | Cod sursa (job #894874) | Cod sursa (job #2909348)
#include <bits/stdc++.h>
#define N 1000005
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
long long ans;
string s;
vector<int> manacher_odd(string s) {
int n = s.size();
s = "$" + s + "^";
vector<int> p(n + 2);
int l = 1, r = 1;
for(int i = 1; i <= n; i++) {
p[i] = max(0, min(r - i, p[l + (r - i)]));
while(s[i - p[i]] == s[i + p[i]]) {
p[i]++;
}
if(i + p[i] > r) {
l = i - p[i], r = i + p[i];
}
}
return vector<int>(begin(p) + 1, end(p) - 1);
}
vector<int> manacher(string s) {
string t;
for(auto c: s) {
t += string("#") + c;
}
auto res = manacher_odd(t + "#");
return vector<int>(begin(res) + 1, end(res) - 1);
}
int main()
{
fin>>s;
vector<int>p=manacher(s);
for(auto x:p) ans+=x/2;
fout<<ans;
return 0;
}